Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
Preprint
Abstract
For $n$-vertex $m$-edge graphs with integer polynomially-bounded costs and capacities, we provide a randomized parallel algorithm for the minimum cost flow problem with $\tilde O(m+n^ {1.5})$ work and $\tilde O(\sqrt{n})$ depth. On moderately dense graphs ($m>n^{1.5}$), our algorithm is the first one to achieve both near-linear work and sub-linear depth. Previous algorithms are either achieving almost optimal work but are highly sequential [Chen, Kyng, Liu, Peng, Gutenberg, Sachdev, FOCS'22], or achieving sub-linear depth but use super-linear work, [Lee, Sidford, FOCS'14], [Orlin, Stein, Oper. Res. Lett.'93]. Our result also leads to improvements for the special cases of max flow, bipartite maximum matching, shortest paths, and reachability. Notably, the previous algorithms achieving near-linear work for shortest paths and reachability all have depth $n^{o(1)}\cdot \sqrt{n}$ [Fischer, Haeupler, Latypov, Roeyskoe, Sulser, SOSA'25], [Liu, Jambulapati, Sidford, FOCS'19]. Our algorithm consists of a parallel implementation of [van den Brand, Lee, Liu, Saranurak, Sidford, Song, Wang, STOC'21]. One important building block is a \emph{dynamic} parallel expander decomposition, which we show how to obtain from the recent parallel expander decomposition of [Chen, Meierhans, Probst Gutenberh, Saranurak, SODA'25].
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- A fast parallel max-flow algorithmJournal of Parallel and Distributed Computing, 2022
- Fully Dynamic s-t Edge Connectivity in Subpolynomial Time (Extended Abstract)2022
- Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time2017
- Parallel algorithms for red–black treesTheoretical Computer Science, 2001
- Parallel algorithms for the assignment and minimum-cost flow problemsOperations Research Letters, 1993
- High-Probability Parallel Transitive-Closure AlgorithmsSIAM Journal on Computing, 1991
- Faster Scaling Algorithms for Network ProblemsSIAM Journal on Computing, 1989
- Matching is as easy as matrix inversionCombinatorica, 1987
- Constructing a perfect matching is in random NCCombinatorica, 1986
- An O(n2log n) parallel max-flow algorithmJournal of Algorithms, 1982