{"id":"arxiv:2406.03648","kind":"preprint","title":"Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time","authors":["Aaron Bernstein","Joakim Blikstad","Thatchaphol Saranurak","Ta-Wei Tu"],"author_count":4,"year":2024,"published":"2024-06-05","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2406.03648","nct_id":null,"source_url":"https://arxiv.org/abs/2406.03648","archive_url":"https://space-kitty.com/papers/arxiv:2406.03648","updated":"2025-09-28","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2406.03648","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"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.","topics":[],"cited_in_dossiers":[]}