An Exponent-Tight Conditional 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)}. \] 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.25875
curl -X POST /api/v1/records/arxiv/2606.25875/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.25875/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'