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 Õ(m + n1.5) work and Õ(√n) depth1. On moderately dense graphs (m > n1.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 [CKL+22], or achieving sub-linear depth but use super-linear work [LS14, OS93]. 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 no(1). √n [JLS19, FHL+25].
Our algorithm consists of a parallel implementation of [BLL+21]. One important building block is a parallel batch-dynamic expander decomposition, which we show how to obtain from the recent parallel expander decomposition of [CMGS25].