pith. machine review for the scientific record. sign in

arxiv: 2604.03412 · v2 · submitted 2026-04-03 · 💻 cs.DS · math.CO

Recognition: 1 theorem link

· Lean Theorem

Improved Upper Bounds for the Directed Flow-Cut Gap

Greg Bodwin , Luba Samborska
Authors on Pith no claims yet

Pith reviewed 2026-05-13 17:51 UTC · model grok-4.3

classification 💻 cs.DS math.CO
keywords directed flow-cut gapupper boundsgraph algorithmsnetwork flowsapproximation algorithmsreductionsedge vertex equivalence
0
0 comments X

The pith

The flow-cut gap for n-node directed graphs is at most n^{1/3 + o(1)}.

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

The paper proves a new upper bound showing that the directed flow-cut gap is at most n to the power of 1/3 plus a little-o term. This improves the long-standing previous upper bound of roughly n to the 11/23 power and brings it closer to the known lower bound of roughly n to the 1/7 power. A sympathetic reader cares because the flow-cut gap quantifies how well fractional solutions can approximate integral cuts in directed networks, which directly affects the design of efficient algorithms for routing and connectivity problems. The work also gives a bound of W to the power 1/2 times n to the little-o, where W sums the minimum fractional cut weights. It further strengthens the toolkit by proving near-equivalence between edge and vertex versions of the gap through an expanded set of reductions.

Core claim

We prove that the flow-cut gap for n-node directed graphs is at most n^{1/3 + o(1)}. This is the first improvement since a previous upper bound of Õ(n^{11/23}) by Agarwal, Alon, and Charikar (STOC '07), and it narrows the gap to the current lower bound of Ω̃(n^{1/7}) by Chuzhoy and Khanna (JACM '09). We also show an upper bound on the directed flow-cut gap of W^{1/2}n^{o(1)}, where W is the sum of the minimum fractional cut weights. As an auxiliary contribution, we significantly expand the network of reductions among various versions of the directed flow-cut gap problem. In particular, we prove near-equivalence between the edge and vertex directed flow-cut gaps, and we show that when paramet

What carries the argument

An expanded network of reductions establishing near-equivalence between edge and vertex versions of the directed flow-cut gap while allowing reduction to unit capacities and uniform fractional cut weights without loss of generality.

If this is right

  • The directed flow-cut gap is bounded above by n^{1/3 + o(1)}.
  • The directed flow-cut gap is also bounded above by W^{1/2} n^{o(1)}.
  • Edge and vertex versions of the directed flow-cut gap are nearly equivalent.
  • Unit-capacity and uniform-weight instances suffice for the W-parametrized bound without loss of generality.
  • The network of reductions among variants of the gap problem is substantially larger than before.

Where Pith is reading between the lines

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

  • Future proofs for one variant of the gap can now be translated to the other variant with only small loss.
  • The remaining gap between the new upper bound and the lower bound of n^{1/7} suggests the true exponent may lie strictly between 1/7 and 1/3.
  • Improved gap bounds can be fed directly into approximation algorithms for directed network-design problems that rely on flow-cut duality.
  • Tighter control over the reductions could eventually allow matching the upper and lower bounds exactly.

Load-bearing premise

The sequence of reductions between edge and vertex versions of the gap and between weighted and unit-capacity instances preserve the gap up to the claimed factors without introducing hidden losses.

What would settle it

A family of directed n-node graphs in which some pair has max-flow to min-cut ratio strictly larger than n^{1/3} by more than any little-o factor.

Figures

Figures reproduced from arXiv: 2604.03412 by Greg Bodwin, Luba Samborska.

Figure 1
Figure 1. Figure 1: An instance (G, P) with unit edge costs/capacities, on which the minimum fractional and integral cuts differ. A minimum integral cut has cost 2 (left), while a minimum fractional cut has cost 3 2 (middle), matching the maximum flow of value 3 2 (right). 1 Introduction We study extensions of the Min-Cut Max-Flow (MCMF) Theorem, a fundamental primitive in graph theory and algorithms. This theorem states that… view at source ↗
Figure 2
Figure 2. Figure 2: The network of reductions proved in this section. The parameter [PITH_FULL_IMAGE:figures/full_fig_p024_2.png] view at source ↗
read the original abstract

We prove that the flow-cut gap for $n$-node directed graphs is at most $n^{1/3 + o(1)}$. This is the first improvement since a previous upper bound of $\widetilde{O}(n^{11/23})$ by Agarwal, Alon, and Charikar (STOC '07), and it narrows the gap to the current lower bound of $\widetilde{\Omega}(n^{1/7})$ by Chuzhoy and Khanna (JACM '09). We also show an upper bound on the directed flow-cut gap of $W^{1/2}n^{o(1)}$, where $W$ is the sum of the minimum fractional cut weights. As an auxiliary contribution, we significantly expand the network of reductions among various versions of the directed flow-cut gap problem. In particular, we prove near-equivalence between the edge and vertex directed flow-cut gaps, and we show that when parametrizing by $W$, one can assume unit capacities and uniform fractional cut weights without loss of generality.

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.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper derives the n^{1/3 + o(1)} bound by expanding a network of reductions (edge-to-vertex, weighted-to-unit-capacity) that are proven to preserve the gap up to n^{o(1)} factors, then directly bounding the reduced special case. These steps are explicit proofs of near-equivalence rather than definitions or fits that make the output equivalent to the input by construction. No load-bearing claim reduces to a self-citation whose content is unverified or to a fitted parameter renamed as a prediction. The argument is self-contained against external benchmarks and prior bounds.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions and axioms of directed graphs, flows, and cuts from prior literature; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • standard math Standard axioms of directed graphs, max-flow min-cut theorem for fractional flows, and basic properties of cuts and capacities.
    The entire development rests on these established graph-theoretic foundations.

pith-pipeline@v0.9.0 · 5476 in / 1109 out tokens · 121145 ms · 2026-05-13T17:51:54.918428+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages · 1 internal anchor

  1. [1]

    Improved approximation for directed cut problems

    Amit Agarwal, Noga Alon, and Moses S Charikar. Improved approximation for directed cut problems. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 671–680, 2007. 30

    work page 2007

  2. [2]

    Probabilistic approximation of metric spaces and its algorithmic applications

    Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. InProceedings of 37th Conference on Foundations of Computer Science, pages 184–193. IEEE, 1996

    work page 1996

  3. [3]

    Negative-weight single-source short- est paths in near-linear time.Communications of the ACM, 68(2):87–94, 2025

    Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen. Negative-weight single-source short- est paths in near-linear time.Communications of the ACM, 68(2):87–94, 2025

    work page 2025

  4. [4]

    Bridge girth: A unifying notion in network design

    Greg Bodwin, Gary Hoppenworth, and Ohad Trabelsi. Bridge girth: A unifying notion in network design. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 600–648. IEEE, 2023

    work page 2023

  5. [5]

    Negative-weight single-source shortest paths in near-linear time: Now faster! In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 515–538

    Karl Bringmann, Alejandro Cassis, and Nick Fischer. Negative-weight single-source shortest paths in near-linear time: Now faster! In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 515–538. IEEE, 2023

    work page 2023

  6. [6]

    Near-Optimal Directed Low- Diameter Decompositions

    Karl Bringmann, Nick Fischer, Bernhard Haeupler, and Rustam Latypov. Near-Optimal Directed Low- Diameter Decompositions. In52nd International Colloquium on Automata, Languages, and Program- ming (ICALP 2025), volume 334, pages 35:1–35:18, 2025

    work page 2025

  7. [7]

    On the hardness of approximating multicut and sparsest-cut.computational complexity, 15:94–114, 2006

    Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D Sivakumar. On the hardness of approximating multicut and sparsest-cut.computational complexity, 15:94–114, 2006

    work page 2006

  8. [8]

    Flow-cut gaps for integer and fractional multiflows.Journal of Combinatorial Theory, Series B, 103(2):248–273, 2013

    Chandra Chekuri, F Bruce Shepherd, and Christophe Weibel. Flow-cut gaps for integer and fractional multiflows.Journal of Combinatorial Theory, Series B, 103(2):248–273, 2013

    work page 2013

  9. [9]

    Approximating directed multicuts

    Joseph Cheriyan, Howard Karloff, and Yuval Rabani. Approximating directed multicuts. InProceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 320–328. IEEE, 2001

    work page 2001

  10. [10]

    Hardness of cut problems in directed graphs

    Julia Chuzhoy and Sanjeev Khanna. Hardness of cut problems in directed graphs. InProceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 527–536, 2006

    work page 2006

  11. [11]

    Polynomial flow-cut gaps and hardness of directed cut problems

    Julia Chuzhoy and Sanjeev Khanna. Polynomial flow-cut gaps and hardness of directed cut problems. Journal of the ACM (JACM), 56(2):1–28, 2009

    work page 2009

  12. [12]

    Flows, cuts and integral routing in graphs-an approximation algorithmist’s perspective

    Julia Chuzoy. Flows, cuts and integral routing in graphs-an approximation algorithmist’s perspective. InProc. of the International Congress of Mathematicians, pages 585–607, 2014

    work page 2014

  13. [13]

    A tight bound on approximating arbitrary metrics by tree metrics

    Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. InProceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 448–455, 2003

    work page 2003

  14. [14]

    A face cover perspective toℓ 1 embeddings of planar graphs.ACM Transactions on Algorithms, 21(1):1–21, 2024

    Arnold Filtser. A face cover perspective toℓ 1 embeddings of planar graphs.ACM Transactions on Algorithms, 21(1):1–21, 2024

    work page 2024

  15. [15]

    Optimal padded decomposition for bounded treewidth graphs.TheoretiCS, 4, 2025

    Arnold Filtser, Tobias Friedrich, Davis Issac, Nikhil Kumar, Hung Le, Nadym Mallek, and Ziena Zeif. Optimal padded decomposition for bounded treewidth graphs.TheoretiCS, 4, 2025

    work page 2025

  16. [16]

    Flows in networks

    Lester Randolph Ford and Delbert Ray Fulkerson. Flows in networks. 2015

    work page 2015

  17. [17]

    Approximate max-flow min-(multi) cut theo- rems and their applications.SIAM Journal on Computing, 25(2):235–251, 1996

    Naveen Garg, Vijay V Vazirani, and Mihalis Yannakakis. Approximate max-flow min-(multi) cut theo- rems and their applications.SIAM Journal on Computing, 25(2):235–251, 1996

    work page 1996

  18. [18]

    Improved results for directed multicut

    Anupam Gupta. Improved results for directed multicut. InSODA, volume 3, pages 454–455, 2003

    work page 2003

  19. [19]

    Cuts, trees andℓ 1-embeddings of graphs.Combinatorica, 24(2):233–269, 2004

    Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Cuts, trees andℓ 1-embeddings of graphs.Combinatorica, 24(2):233–269, 2004. 31

    work page 2004

  20. [20]

    Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation

    Bernhard Haeupler, Richard Hlad´ ık, Shengzhe Wang, and Zhijun Zhang. Stronger directed low-diameter decompositions with sub-logarithmic diameter and separation.arXiv preprint arXiv:2509.24565, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  21. [21]

    Ano(√n)-approximation algorithm for directed spars- est cut.Information Processing Letters, 97(4):156–160, 2006

    Mohammad Taghi Hajiaghayi and Harald R¨ acke. Ano(√n)-approximation algorithm for directed spars- est cut.Information Processing Letters, 97(4):156–160, 2006

    work page 2006

  22. [22]

    Embeddings of planar quasimetrics into directed ℓ1 and polylogarithmic approximation for directed sparsest-cut

    Ken-ichi Kawarabayashi and Anastasios Sidiropoulos. Embeddings of planar quasimetrics into directed ℓ1 and polylogarithmic approximation for directed sparsest-cut. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 480–491. IEEE, 2022

    work page 2022

  23. [23]

    Greedy approximation algorithms for directed multicuts

    Yana Kortsarts, Guy Kortsarz, and Zeev Nutov. Greedy approximation algorithms for directed multicuts. Networks: An International Journal, 45(4):214–217, 2005

    work page 2005

  24. [24]

    Flow-cut gaps and face covers in planar graphs

    Robert Krauthgamer, James R Lee, and Havana Rika. Flow-cut gaps and face covers in planar graphs. InProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 525–534. SIAM, 2019

    work page 2019

  25. [25]

    A node-capacitated okamura-seymour theo- rem

    James R Lee, Manor Mendel, and Mohammad Moharrami. A node-capacitated okamura-seymour theo- rem. InProceedings of the forty-fifth annual ACM symposium on Theory of Computing, pages 495–504, 2013

    work page 2013

  26. [26]

    Pathwidth, trees, and random embeddings.Combinatorica, 33(3):349–374, 2013

    James R Lee and Anastasios Sidiropoulos. Pathwidth, trees, and random embeddings.Combinatorica, 33(3):349–374, 2013

    work page 2013

  27. [27]

    Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.Journal of the ACM (JACM), 46(6):787–832, 1999

    Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.Journal of the ACM (JACM), 46(6):787–832, 1999

    work page 1999

  28. [28]

    Multicommodity flows in planar graphs.Journal of Combina- torial Theory, Series B, 31(1):75–81, 1981

    Haruko Okamura and Paul D Seymour. Multicommodity flows in planar graphs.Journal of Combina- torial Theory, Series B, 31(1):75–81, 1981

    work page 1981

  29. [29]

    Small distortion and volume preserving embeddings for planar and euclidean metrics

    Satish Rao. Small distortion and volume preserving embeddings for planar and euclidean metrics. In Proceedings of the fifteenth annual symposium on Computational geometry, pages 300–306, 1999

    work page 1999

  30. [30]

    Transitive-closure spanners: A survey

    Sofya Raskhodnikova. Transitive-closure spanners: A survey. InProperty testing, pages 167–196. Springer, 2010

    work page 2010

  31. [31]

    A lower bound on the integrality gap for minimum multicut in directed networks.Combinatorica, 24(3):525–530, 2004

    Michael Saks, Alex Samorodnitsky, and Leonid Zosin. A lower bound on the integrality gap for minimum multicut in directed networks.Combinatorica, 24(3):525–530, 2004

    work page 2004

  32. [32]

    On constant multi-commodity flow-cut gaps for directed minor-free graphs.arXiv preprint arXiv:1711.01370, 2017

    Ario Salmasi, Anastasios Sidiropoulos, and Vijay Sridhar. On constant multi-commodity flow-cut gaps for directed minor-free graphs.arXiv preprint arXiv:1711.01370, 2017. 32

    work page arXiv 2017