Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs

We give a combinatorial algorithm for computing exact maximum flows in directed graphs with n vertices and edge capacities from 1, …, U in $\tilde O\left({{n^2}\log U}\right)$ time, which is near-optimal on dense graphs. This shaves an no(1)factor from the recent result of [Bernstein–Blikstad–Saranurak–Tu FOCS’24] and, more importantly, greatly simplifies their algorithm. We believe that ours is by a significant margin the simplest of all algorithms that go beyond $\tilde O(m\sqrt n )$ time in general graphs. To highlight this relative simplicity, we provide a full implementation of the algorithm in C++.The only randomized component of our work is the cut-matching game. Via existing tools, we show how to derandomize it for vertex-capacitated max flow and obtain a deterministic $\tilde O\left({{n^2}}\right)$ time algorithm. This marks the first deterministic near-linear time algorithm for this problem (or even for the special case of bipartite matching) in any density regime.