Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern

Speaker(s)

Florian Hörsch

Affiliation

CISPA

Language of the talk

English

Date

April 4, 2025, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

The Multicut problem asks for a minimum cut separating certain
pairs of vertices: formally, given a graph G and a demand graph H on a
set T ⊆ V (G) of terminals, the task is to find a minimum-weight set C of
edges of G such that whenever two vertices of T are adjacent in H, they
are in different components of G \ C.
This problem is NP-hard in general graphs even if H contains only 3
terminals, but turns out to be much better tractable in planar graphs.
Colin de Verdière showed that Multicut with t terminals on a planar
graph G can be solved in time f (t)nO(√t). Marx proved a matching lower
bound showing that the exponent of n is essentially best possible, even
when the demand graph H is a complete graph.
However, this lower bound tells us nothing about other special cases,
for example when H is a complete bipartite or tripartite graph. We show
that if H is, in some sense, close to being a complete bipartite graph, then
Multicut can be solved faster than f (t)nO(√t), and furthermore, this is
the only property that allows such an improvement.
This is joint work with Jacob Focke, Shaohua Li, and Dániel Marx.

---