Maximum Flow Without the Outer IPM

Abstract

We show that the balancing weights technique of Li (2026) actually produces an approximate *pseudo-circulation* of a directed, capacitated graph in $m^{1+o(1)}$ time. Together with standard flow techniques, we obtain an $m^{1+o(1)}$ time maximum flow algorithm that avoids the interior-point method framework of recent almost-linear time algorithms (Chen et al. FOCS 2022, van den Brand et al. FOCS 2024).

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.