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 \approx n^{1.5}$), our algorithm is the first to achieve both near-linear work and sub-linear depth. Previous algorithms either achieve almost optimal work but are highly sequential [Chen, Kyng, Liu, Peng, Gutenberg, Sachdev, FOCS'22], or achieve 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 special cases such as max flow, bipartite maximum matching, shortest paths, and reachability. Notably, previous algorithms achieving near-linear work for shortest paths and reachability all have depth $n^{o(1)} \times \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 dynamic parallel expander decomposition, which we show how to obtain from the recent parallel expander decomposition of [Chen, Meierhans, Probst Gutenberg, Saranurak, SODA'25].
Blogger's Review: The proposed algorithm represents a significant theoretical breakthrough in solving the minimum cost flow problem for dense graphs, particularly in balancing work and depth. Future research could explore the algorithm's potential applications in other graph theory problems.