A Stronger Conditional Running-Time Lower Bound for Global Label Min-Cut
For researchers in fine-grained complexity, this provides a tighter lower bound for a fundamental graph problem, though it is an incremental improvement over prior work.
The paper strengthens the conditional running-time lower bound for the global label min-cut problem from (np)^{o(log n/(log log n)^2)} to (np)^{o(log n/log log n)} under the Exponential Time Hypothesis.
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\left(\frac{\log n}{\log\log n}\right)}. \]