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

Yuanhao Wang, Wei Wang, Kehua Wang

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)…