  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(\log
\mathrm{OPT})}$-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(\log n/ (\log \log 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. To turn this lower bound into a quasi-polynomial-time lower bound,
we also needed to revisit the framework due to Marx [Theory Comput. 2010] of
proving lower bounds assuming Exponential Time Hypothesis through the Subgraph
Isomorphism problem parameterized by the number of edges of the pattern. Here,
we provide an alternative simplified proof of the hardness of this problem that
is more versatile with respect to the choice of the regimes of the parameters.

Data Structures and Algorithms;Computational Complexity