{"id":"arxiv/2604.03412","url":"https://arxiv.org/abs/2604.03412","tags":["cs.DS","math.CO"],"score":0,"title":"Improved Upper Bounds for the Directed Flow-Cut Gap","domain":"cs.DS","source":"arxiv","authors":["Greg Bodwin","Luba Samborska"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-03","reactions":{}}