{"id":"arxiv/2606.25875","url":"https://arxiv.org/abs/2606.25875","tags":["cs.DS","math.CO"],"score":0,"title":"An Exponent-Tight Conditional Lower Bound for Global Label Min-Cut","domain":"cs.DS","source":"arxiv","authors":["Yuanhao Wang","Kehua Wang","Wei Wang"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-24","reactions":{}}