Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances

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 [18], or achieving sub-linear depth but use super-linear work [49, 62]. 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} \) [26, 33].

Our algorithm consists of a parallel implementation of [11]. One important building block is a parallel batch-dynamic expander decomposition, which we show how to obtain from the recent parallel expander decomposition of [17].

Other versions. An extended abstract of this paper was previously published in the Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2025.