Improved Upper Bounds for the Directed Flow-Cut Gap

Greg Bodwin, Luba Samborska

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 $\tilde{O}(n^{11/23})$ by…