Improved Upper Bounds for the Directed Flow-Cut Gap
This work advances the theoretical understanding of the flow-cut gap in directed graphs, a fundamental problem in combinatorial optimization and approximation algorithms.
The paper improves the upper bound on the directed flow-cut gap for n-node graphs from Õ(n^{11/23}) to n^{1/3+o(1)}, narrowing the gap to the lower bound of Ω̃(n^{1/7}). It also provides an upper bound of W^{1/2}n^{o(1)} where W is the sum of minimum fractional cut weights.
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.