2023/12/18 by Focke, Jacob, Hörsch, Florian, Li, Shaohua +1
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2312.11086
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⊆ 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. 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)nO(√(g2+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)nO(√(g2+gt+t)), and furthermore this is the only property that allows such an improvement. Formally, for a class H of graphs, Multicut(H) is the special case where the demand graph H is in H. For every fixed class 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(H).