Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
Jacob Focke, Florian Hörsch, Shaohua Li, Dániel Marx · arXiv (Cornell University) · 2023
The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph G and 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 fixed values 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. 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, 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 Multicut(\mathcal{H}). In addition, we investigate a similar setting where, instead of parameterizing by the genus g of G, we parameterize by the minimum number k of edges of G that need to be deleted to obtain a planar graph. Interestingly, in this setting it makes a significant difference whether the graph G is weighted or unweighted: further nontrivial algorithmic techniques give substantial improvements in the unweighted case.