A Stronger Conditional Running-Time Lower Bound for Global Label Min-Cut

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)}\mathrm{.}$$ In this paper, we give a deterministic reduction that strengthens this conditional running-time lower bound to $$(np{)}^{o\left(\frac{\log n}{\log \log n}\right)}\mathrm{.}$$