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)\) 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\) . 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})}\) . 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})}\) , and furthermore this is the only property that allows such an improvement. Formally, for a class \(\mathcal {H}\) of graphs, \(\textsc {Multicut}(\mathcal {H})\) is the special case where the demand graph H is in \(\mathcal {H}\) . For every fixed class \(\mathcal {H}\) (satisfying some mild closure property), fixed g, and fixed t, our main result gives tight upper and lower bounds on the exponent of n in algorithms solving \(\textsc {Multicut}(\mathcal {H})\) .
