Parallel (1+ε)-Approximate Multi-Commodity Min-Cost Flow in Almost Optimal Depth and Work

We present a parallel algorithm for computing ($1+ \epsilon$)-approximate min-cost flow on an undirected graph with m edges, where capacities and costs are assigned to both edges and vertices. Our algorithm achieves $\hat{O}(m)$ work and $\hat{O}(1)$ depth when $\epsilon\gt 1 / \operatorname{polylog}(m)$, making both the work and depth almost optimal, up to a subpolynomial factor. Previous algorithms with $\hat{O}(m)$ work required $\Omega(m)$ depth, even for special cases of min-cost flow with only edge capacities or max flow with vertex capacities. Our result generalizes prior almost-optimal parallel $(1+\epsilon)$-approximation algorithms for these special cases, including shortest paths [1]–[3] and max flow with only edge capacities [4], [5]. Our key technical contribution is the first construction of length-constrained flow shortcuts with $(1+\epsilon)$ length slack, $\hat{O}(1)$ congestion slack, and $\hat{O}(1)$ step bound. This provides a strict generalization of the influential concept of $(\hat{O}(1), \epsilon)$-hopsets [6], allowing for additional control over congestion. Previous lengthconstrained flow shortcuts [7] incur a large constant in the length slack, which would lead to a large approximation factor. To enable our flow algorithms to work under vertex capacities, we also develop a close-to-linear time algorithm for computing length-constrained vertex expander decomposition. Building on Cohen’s idea of path-count flows [8], we further extend our algorithm to solve $(1+\epsilon)$-approximate k-commodity min-cost flow problems with almost-optimal $\hat{O}(m k)$ work and $\hat{O}(1)$ depth, independent of the number of commodities k.