pith. sign in

arxiv: 2606.25875 · v1 · pith:DJPCSMU3new · submitted 2026-06-24 · 💻 cs.DS · math.CO

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

Yuanhao Wang , Wei Wang This is my paper

Pith reviewed 2026-06-25 19:22 UTC · model grok-4.3

classification 💻 cs.DS math.CO
keywords conditional lower boundsexponential time hypothesisglobal label min-cutdeterministic reductionsgraph algorithmsrunning time complexity
0
0 comments X

The pith

A deterministic reduction strengthens the ETH lower bound for Global Label Min-Cut to (np) raised to o(log n over log log n).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a deterministic reduction that improves an existing conditional lower bound on the running time of algorithms for the Global Label Min-Cut problem. Previous work established that, assuming the Exponential Time Hypothesis, no deterministic algorithm can run in time (np) to the power of o(log n over (log log n) squared). This new reduction raises the lower bound to (np) to the power of o(log n over log log n). A reader would care because it shows that solving this graph problem is likely to require more time than previously thought under standard complexity assumptions.

Core claim

The authors give a deterministic reduction that strengthens the conditional running-time lower bound for Global Label Min-Cut to (np)^{o(log n / log log n)}.

What carries the argument

A deterministic reduction that composes with the prior hardness result to improve the exponent in the lower bound.

If this is right

  • Under ETH, no deterministic algorithm solves Global Label Min-Cut in time (np)^{o(log n / log log n)}.
  • The prior lower bound of (np)^{o(log n / (log log n)^2)} is strictly improved by removing one log log n factor from the denominator.
  • Any algorithm achieving the new bound would match the strengthened conditional limit.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction technique could potentially strengthen lower bounds for other problems in labeled graph optimization.
  • Closing the remaining gap to a (np)^{o(log n)} bound would require a different reduction strategy.

Load-bearing premise

The new deterministic reduction correctly composes with the prior hardness result to transfer the ETH assumption into the improved exponent.

What would settle it

A deterministic algorithm solving Global Label Min-Cut in time (np)^{o(log n / log log n)} would falsify the strengthened lower bound.

read the original abstract

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)}. \]

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper claims to provide a deterministic reduction strengthening the ETH-based conditional lower bound for Global Label Min-Cut from (np)^{o(log n / (log log n)^2)} to (np)^{o(log n / log log n)}.

Significance. If the reduction is correct and composes without introducing extra logarithmic factors in the exponent, the result tightens the known hardness threshold for this problem under ETH. This would be a modest but concrete advance in fine-grained complexity for labeled cut problems.

major comments (1)
  1. [Abstract] Abstract: the central claim is the existence of a deterministic reduction achieving the improved exponent, yet the abstract provides no construction, no analysis of the (n,p) parameter blowup, and no verification that the reduction preserves the exact ETH gap without additional (log log n) factors. This is the load-bearing step; without it the strengthened bound cannot be confirmed.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their feedback. The manuscript provides a full deterministic reduction with the claimed properties; we address the specific concern about the abstract below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim is the existence of a deterministic reduction achieving the improved exponent, yet the abstract provides no construction, no analysis of the (n,p) parameter blowup, and no verification that the reduction preserves the exact ETH gap without additional (log log n) factors. This is the load-bearing step; without it the strengthened bound cannot be confirmed.

    Authors: Abstracts are concise summaries and do not contain constructions or full analyses; those appear in the body. Section 3 gives the explicit deterministic reduction from 3-SAT, Section 4 analyzes the (n,p) blowup (which remains polynomial with no extra log-log factors in the exponent), and the ETH gap is preserved exactly as stated in Theorem 1.1. The abstract correctly summarizes the final bound without needing to embed the full proof. revision: no

Circularity Check

0 steps flagged

No circularity; new deterministic reduction is independent contribution

full rationale

The paper's central claim is the construction of a new deterministic reduction that composes with a prior ETH-based hardness result to improve the exponent in the conditional lower bound for Global Label Min-Cut. This reduction is presented as the novel technical contribution and is not shown to be equivalent to its inputs by definition, a fitted parameter, or a self-citation chain. The derivation relies on an external assumption (ETH) and prior work, but the reduction itself does not reduce to any of the enumerated circular patterns. The paper is self-contained in its claim of providing an explicit strengthening via reduction, with no load-bearing self-citation or ansatz smuggling evident from the provided text.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the Exponential Time Hypothesis (a standard domain assumption in fine-grained complexity) together with the correctness of an unspecified deterministic reduction.

axioms (1)
  • domain assumption Exponential Time Hypothesis (ETH)
    The lower bound is conditional on ETH, invoked in the abstract as the source of the prior hardness result.

pith-pipeline@v0.9.1-grok · 5607 in / 1053 out tokens · 25492 ms · 2026-06-25T19:22:28.093977+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 20 canonical work pages

  1. [1]

    D. R. Karger and C. Stein. A New Approach to the Minimum Cut Problem.Journal of the ACM, 43(4):601–640, 1996. doi:10.1145/234533.234534

    work page doi:10.1145/234533.234534 1996

  2. [2]

    D. R. Karger. Minimum Cuts in Near-Linear Time.Journal of the ACM, 47(1):46–76,

  3. [3]

    doi:10.1145/331605.331608

    work page doi:10.1145/331605.331608

  4. [4]

    Stoer and F

    M. Stoer and F. Wagner. A Simple Min-Cut Algorithm.Journal of the ACM, 44(4):585–591, 1997. doi:10.1145/263867.263872. 19

    work page doi:10.1145/263867.263872 1997

  5. [5]

    Coudert, P

    D. Coudert, P. Datta, S. Pérennes, H. Rivano, and M.-E. Voge. Shared risk re- source group: Complexity and approximability issues.Parallel Processing Letters, 17(2):169–184, 2007. doi:10.1142/S0129626407002958

    work page doi:10.1142/s0129626407002958 2007

  6. [6]

    Coudert, S

    D. Coudert, S. Pérennes, H. Rivano, and M.-E. Voge. Combinatorial optimization in networks with shared risk link groups.Discrete Mathematics & Theoretical Computer Science, 18(3), 2016. doi:10.46298/dmtcs.1297

    work page doi:10.46298/dmtcs.1297 2016

  7. [7]

    Ghaffari, D

    M. Ghaffari, D. R. Karger, and D. Panigrahi. Random Contractions and Sampling for Hypergraph and Hedge Connectivity. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1101–1114,

  8. [8]

    doi:10.1137/1.9781611974782.71

    work page doi:10.1137/1.9781611974782.71

  9. [9]

    Jaffke, P

    L. Jaffke, P. T. de Lima, T. Masařík, M. Pilipczuk, and U. S. Souza. A Tight Quasi- Polynomial Bound for Global Label Min-Cut.ACM Transactions on Algorithms, 22(2), Article 23, pages 1–12, 2026. doi:10.1145/3796220

    work page doi:10.1145/3796220 2026

  10. [10]

    F. V. Fomin, P. A. Golovach, T. Korhonen, D. Lokshtanov, and S. Saurabh. Fixed-Parameter Tractability of Hedge Cut. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1402–1411, 2025. doi:10.1137/1.9781611978322.43

    work page doi:10.1137/1.9781611978322.43 2025

  11. [11]

    Chekuri and C

    C. Chekuri and C. Xu. Minimum Cuts and Sparsification in Hypergraphs.SIAM Journal on Computing, 47(6):2118–2156, 2018. doi:10.1137/18M1163865

    work page doi:10.1137/18m1163865 2018

  12. [12]

    K. Fox, D. Panigrahi, and F. Zhang. Minimum Cut and Minimumk-Cut in Hypergraphs via Branching Contractions. InProceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 881–896, 2019. doi:10.1137/1.9781611975482.54

    work page doi:10.1137/1.9781611975482.54 2019

  13. [13]

    Zhang, J.-Y

    P. Zhang, J.-Y. Cai, L.-Q. Tang, and W.-B. Zhao. Approximation and Hardness Results for Label Cut and Related Problems.Journal of Combinatorial Optimization, 21(2):192–208, 2011. doi:10.1007/s10878-009-9222-0

    work page doi:10.1007/s10878-009-9222-0 2011

  14. [14]

    Tang and P

    L. Tang and P. Zhang. Approximating Minimum Labels–t Cut via Linear Program- ming. InLATIN 2012, Lecture Notes in Computer Science 7256, pages 655–666,

    2012

  15. [15]

    doi:10.1007/978-3-642-29344-3_55

    work page doi:10.1007/978-3-642-29344-3_55

  16. [16]

    M. R. Fellows, J. Guo, and I. Kanj. The parameterized complexity of some minimum label problems.Journal of Computer and System Sciences, 76(8):727–740, 2010. doi:10.1016/j.jcss.2010.02.012

    work page doi:10.1016/j.jcss.2010.02.012 2010

  17. [17]

    Zhang and B

    P. Zhang and B. Fu. The Label Cut Problem with Respect to Path Length and Label Frequency.Theoretical Computer Science, 648:72–83, 2016. doi:10.1016/j.tcs.2016.08.006

    work page doi:10.1016/j.tcs.2016.08.006 2016

  18. [18]

    Zhang, B

    P. Zhang, B. Fu, and L. Tang. Simpler and Better Approximation Algorithms for the Unweighted Minimum Labels–t Cut Problem.Algorithmica, 80(1):398–409,

  19. [19]

    doi:10.1007/s00453-016-0265-1

    work page doi:10.1007/s00453-016-0265-1

  20. [20]

    D. Marx. Can You Beat Treewidth?Theory of Computing, 6(1):85–112, 2010. doi:10.4086/toc.2010.v006a005. 20

    work page doi:10.4086/toc.2010.v006a005 2010

  21. [21]

    J. Chen, X. Huang, I. A. Kanj, and G. Xia. Strong Computational Lower Bounds via Parameterized Complexity.Journal of Computer and System Sciences, 72(8):1346– 1367, 2006. doi:10.1016/j.jcss.2006.04.007

    work page doi:10.1016/j.jcss.2006.04.007 2006

  22. [22]

    and Kowalik, ukasz and Lokshtanov, Daniel and Marx, D\'aniel and Pilipczuk, Marcin and Pilipczuk, Micha

    M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.Parameterized Algorithms. Springer, Cham, 2015. doi:10.1007/978-3-319-21275-3

    work page doi:10.1007/978-3-319-21275-3 2015

  23. [23]

    Hammack, W

    R. Hammack, W. Imrich, and S. Klavžar.Handbook of Product Graphs, 2nd edition. CRC Press, Boca Raton, 2011

    2011

  24. [24]

    25, American Mathematical Society, Providence, RI, 1967

    G.Birkhoff.Lattice Theory, 3rdedition.AmericanMathematicalSocietyColloquium Publications, Vol. 25, American Mathematical Society, Providence, RI, 1967

    1967

  25. [25]

    On the Complexity of k-SAT , journal =

    R. Impagliazzo and R. Paturi. On the Complexity ofk-SAT.Journal of Computer and System Sciences, 62(2):367–375, 2001. doi:10.1006/jcss.2000.1727

    work page doi:10.1006/jcss.2000.1727 2001

  26. [26]

    Which Problems Have Strongly Exponential Complexity?

    R. Impagliazzo, R. Paturi, and F. Zane. Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 63(4):512–530, 2001. doi:10.1006/jcss.2001.1774. 21

    work page doi:10.1006/jcss.2001.1774 2001