# Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time

Preprint · Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak, Ta-Wei Tu

- Archive id: arxiv:2406.03648
- Published: 2024-06-05
- arXiv: https://arxiv.org/abs/2406.03648
- Source URL: https://arxiv.org/abs/2406.03648
- PDF: https://arxiv.org/pdf/2406.03648
- Provenance: arxiv

## Abstract

We present a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from $\\{1,\\dots,U\\}$ in $n^{2+o(1)}\\log U$ time, which is almost optimal in dense graphs. Our algorithm is a novel implementation of the classical augmenting-path framework; we list augmenting paths more efficiently using a new variant of the push-relabel algorithm that uses additional edge weights to guide the algorithm, and we derive the edge weights by constructing a directed expander hierarchy. Even in unit-capacity graphs, this breaks the long-standing $O(m\\cdot\\min\\{\\sqrt{m},n^{2/3}\\})$ time bound of the previous combinatorial algorithms by Karzanov (1973) and Even and Tarjan (1975) when the graph has $m=ω(n^{4/3})$ edges. Notably, our approach does not rely on continuous optimization nor heavy dynamic graph data structures, both of which are crucial in the recent developments that led to the almost-linear time algorithm by Chen et al. (FOCS 2022). Our running time also matches the $n^{2+o(1)}$ time bound of the independent combinatorial algorithm by Chuzhoy and Khanna (STOC 2024) for computing the maximum bipartite matching, a special case of maximum flow.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.