Improved Upper Bounds for the Directed Flow-Cut Gap

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 $\tilde{O}(n^{11/23})$ by Agarwal, Alon, and Charikar (STOC '07), and it narrows the gap to the current lower bound of $\tilde{\hat{I}}\text{c◯}(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.

FOCS 2026