Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917027191455744 |
|---|---|
| author | Bernstein, Aaron Blikstad, Joakim Li, Jason Saranurak, Thatchaphol Tu, Ta-Wei |
| author_facet | Bernstein, Aaron Blikstad, Joakim Li, Jason Saranurak, Thatchaphol Tu, Ta-Wei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_17182 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs Bernstein, Aaron Blikstad, Joakim Li, Jason Saranurak, Thatchaphol Tu, Ta-Wei Data Structures and Algorithms 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. |
| title | Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.17182 |