Improved Upper Bounds for the Directed Flow-Cut Gap
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908950223388672 |
|---|---|
| author | Bodwin, Greg Samborska, Luba |
| author_facet | Bodwin, Greg Samborska, Luba |
| contents | 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Ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_03412 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Improved Upper Bounds for the Directed Flow-Cut Gap Bodwin, Greg Samborska, Luba Data Structures and Algorithms Combinatorics 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Ω(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. |
| title | Improved Upper Bounds for the Directed Flow-Cut Gap |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2604.03412 |