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

Abstract 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\subseteq V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>T</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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\setminus C$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>\</mml:mo> <mml:mi>C</mml:mi> </mml:mrow> </mml:math> . Colin de Verdière [ Algorithmica, 2017] showed that Multicut with t terminals on a graph G of genus g can be solved in time $$f(t,g)n^{O(\sqrt{g^2+gt+t})}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>,</mml:mo> <mml:mi>g</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mrow> <mml:msup> <mml:mi>g</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>+</mml:mo> <mml:mi>g</mml:mi> <mml:mi>t</mml:mi> <mml:mo>+</mml:mo> <mml:mi>t</mml:mi> </mml:mrow> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> . Cohen-Addad et al. [ JACM , 2021] proved a matching lower bound showing that the exponent of n is essentially best possible (for every fixed value of t and g ), even in the special case of Multiway Cut , where the demand graph H is a complete graph. However, this lower bound tells us nothing about other special cases of Multicut such as Group 3-Terminal Cut (where three groups of terminals need to be separated from each other). We show that if the demand pattern is, in some sense, close to being a complete bipartite graph, then Multicut can be solved faster than $$f(t,g)n^{O(\sqrt{g^2+gt+t})}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>,</mml:mo> <mml:mi>g</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mrow> <mml:msup> <mml:mi>g</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>+</mml:mo> <mml:mi>g</mml:mi> <mml:mi>t</mml:mi> <mml:mo>+</mml:mo> <mml:mi>t</mml:mi> </mml:mrow> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> , and furthermore this is the only property that allows such an improvement. Formally, for a class $$\mathcal {H}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> of graphs, $$\textsc {Multicut}(\mathcal {H})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>M</mml:mi> <mml:mstyle> <mml:mi>U</mml:mi> <mml:mi>L</mml:mi> <mml:mi>T</mml:mi> <mml:mi>I</mml:mi> <mml:mi>C</mml:mi> <mml:mi>U</mml:mi> <mml:mi>T</mml:mi> </mml:mstyle> <mml:mo>(</mml:mo> <mml:mi>H</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is the special case where the demand graph H is in $$\mathcal {H}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> . For every fixed class $$\mathcal {H}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi>