{"ID":2852575,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.17182","arxiv_id":"2510.17182","title":"Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs","abstract":"We give a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from $\\{1,\\dots,U\\}$ in $\\tilde{O}(n^{2}\\log U)$ time, which is near-optimal on dense graphs. This shaves an $n^{o(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}(n^2)$ 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.","short_abstract":"We give a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from $\\{1,\\dots,U\\}$ in $\\tilde{O}(n^{2}\\log U)$ time, which is near-optimal on dense graphs. This shaves an $n^{o(1)}$ factor from the recent result of [Bernstein-Blikstad-Saranurak-Tu FOCS'24]...","url_abs":"https://arxiv.org/abs/2510.17182","url_pdf":"https://arxiv.org/pdf/2510.17182v1","authors":"[\"Aaron Bernstein\",\"Joakim Blikstad\",\"Jason Li\",\"Thatchaphol Saranurak\",\"Ta-Wei Tu\"]","published":"2025-10-20T05:56:21Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}