Maximum Flow by Augmenting Paths in n^(2+o(1)) Time

Even in unit-capacity graphs, this breaks the long-standing O(m⋅min{sqtrt(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.

Talk based on paper: "Maximum Flow by Augmenting Paths in n^(2+o(1)) Time", to appear in FOCS 2024, https://arxiv.org/abs/2406.03648.
Joint work with Aaron Bernstein, Thatchaphol Saranurak, Ta-Wei Tu.