Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ TimeOberseminar Discrete Optimization

by Joakim Blikstad (CWI Amsterdam)

Monday Jul 21, 2025, 10:15 AM → 11:15 AM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

The talk will cover a recent line of combinatorial algorithm for computing exact maximum flows in directed graphs with n vertices and edge capacities O(n^2 log^26 n) time, which is near-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.

While not yet efficient, it is to our knowledge the first maximum flow algorithm faster than O(m sqrt m) that has been fully implemented in code.

The talk assumes no prior knowledge in graph algorithms. It is based on the papers:

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

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs. FOCS 2025.

 

Joint work with: Aaron Bernstein, Jason Li, Thachaphol Saranurak, Ta-Wei Tu