Abstract: In this talk, I will present a new combinatorial algorithm for maximum flow that is based on running the weighted push-relabel algorithm introduced in [BBST'24] on "shortcut" graphs. The use of shortcuts not only improves the running time from $n^{2+o(1)}$ to $\tilde{O}(n^2)$ (i.e., near-linear in dense graphs), but, more importantly, also greatly simplifies both the algorithm and analysis.
Our algorithm is randomized but only because of the use of standard randomized cut-matching game. Therefore, using existing alternatives, we also give a deterministic $\tilde{O}(n^2)$ time algorithm for "vertex-capacitated" max-flow. This is the first near-linear time such algorithm in any density regime.
Based on joint work with Aaron Bernstein, Joakim Blikstad, Jason Li, and Thatchaphol Saranurak.