An Exponent-Tight Conditional Lower Bound for Global Label Min-Cut

Abstract

Let $n$ and $p$ denote the numbers of vertices and labels, respectively, in an undirected edge-labeled graph. Previous work showed that, under the Exponential Time Hypothesis (ETH), there is no deterministic algorithm with running time \[ (np)^{o\left(\frac{\log n}{(\log\log n)^2}\right)}. \] In this paper, we give a deterministic reduction that strengthens this conditional running-time lower bound to \[ (np)^{o(\log n)}\operatorname{poly}(|E|). \] The lower bound holds even for simple edge-labeled graphs. Since our reduction is deterministic, the same lower bound applies to bounded-error randomized algorithms under the randomized Exponential Time Hypothesis. On the resulting hard family, $p=n^{O(1)}$. Thus, under rETH, the lower bound matches the exponent order of the known randomized quasi-polynomial exact upper bound up to constant factors.