A Tight Quasi-Polynomial Bound for Global Label Min-Cut

We study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut): the edges of the input (multi) graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the \ (st\) -cut version of the problem is known to be \ (NP\) -hard, the above global cut version is known to admit a quasi-polynomial randomized \ (n^O () \) -time algorithm due to Ghaffari, Karger, and Panigrahi SODA 2017. They consider this as “strong evidence that this problem is in P ”. We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time \ ( (np) ^o (n/ (n) ^{2) }\) would contradict the Exponential Time Hypothesis, where \ (n\) is the number of vertices, and \ (p\) is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is \ (W\) 1-hard when parameterized by the number of uncut labels. In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph.