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

Jan van den Brand, Hossein Gholizadeh, Yonggang Jiang, Tijn de Vos

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 to achieve both near-linear work and sub-linear depth. Previous algorithms either achieved almost optimal work but were highly sequential, or achieved sub-linear depth but used super-linear work. 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}$. Our algorithm consists of a parallel implementation of the framework by van den Brand et al. (STOC'21). A key building block is a dynamic parallel expander decomposition, which we derive from recent parallel expander decomposition techniques.

Introduction

The Minimum Cost Flow (min-cost flow) problem is a fundamental challenge in combinatorial optimization. Given a directed graph where edges have specific capacities and costs, the goal is to route a required amount of flow from sources to sinks at the minimum possible cost. While sequential algorithms for this problem have reached near-optimal efficiency, parallelizing these solutions has historically forced a compromise between two critical metrics:

  1. Work: The total number of operations (ideally matching the best sequential algorithm).
  2. Depth: The longest chain of dependent operations (representing the time required given unlimited processors).

Historically, researchers faced a binary choice: use work-efficient algorithms that were highly sequential (high depth), or use fast parallel algorithms (low depth) that performed significantly more total work than their sequential counterparts. This paper bridges that gap for dense graph instances, achieving near-linear work and square-root depth simultaneously.

Methodology: Parallelizing the Interior Point Method

The algorithm is built upon a modern Interior Point Method (IPM) framework. IPMs solve optimization problems by traversing a "central path" through the interior of a feasible region using iterative Newton steps. To make this framework efficient in a parallel setting, the authors focused on parallelizing the data structures required for each IPM iteration.

Dynamic Parallel Expander Decomposition

The most significant technical hurdle in parallelizing state-of-the-art flow algorithms is maintaining a graph partition known as an expander decomposition. Expanders are subgraphs that are well-connected and lack bottlenecks, making them ideal for sampling edges and maintaining "Lewis weights" (a metric for edge importance).

While static parallel expander decompositions existed, the IPM requires a dynamic version that can handle edge deletions as the algorithm progresses. The authors developed a novel dynamic parallel expander decomposition that supports low-depth updates, effectively removing the sequential bottleneck that hindered previous attempts to parallelize IPM-based flow solvers.

Data Structure Maintenance

Beyond the decomposition, the algorithm parallelizes the maintenance of primal solutions, gradients, and dual variables. By utilizing sketching techniques and matrix-vector products, the authors ensure that updates to these variables are naturally suited for parallel execution. They employ a "heavy hitter" approach, where the algorithm only updates entries that have changed significantly, preserving work efficiency without sacrificing the accuracy of the central path.

Key Results and Complexity

The algorithm achieves a work complexity of $\tilde{O}(m + n^{1.5})$ and a depth of $\tilde{O}(\sqrt{n})$.

Performance on Dense Graphs

For "moderately dense" graphs—specifically those where the number of edges $m$ is at least $n^{1.5}$—the $n^{1.5}$ term is subsumed by $m$. In these cases, the algorithm achieves near-linear work. This represents a major improvement over previous benchmarks:

  • Lee and Sidford (2014): Required $O(m\sqrt{n})$ work for the same $\tilde{O}(\sqrt{n})$ depth.
  • Sequential Breakthroughs: While recent sequential algorithms achieved near-linear work, their depth was often $O(m)$, making them unsuitable for parallel architectures.

Impact on Special Cases

Because min-cost flow is a general problem, these improvements propagate to several other graph problems. For Shortest Paths and Reachability, the algorithm improves the depth from $n^{0.5+o(1)}$ to a cleaner $\tilde{O}(\sqrt{n})$ for dense instances, removing the small $n^{o(1)}$ factor that characterized previous state-of-the-art results.

Conclusion and Future Directions

This research provides the first algorithm to achieve the "sweet spot" of near-linear work and sub-linear depth for dense min-cost flow instances. However, two primary challenges remain for future work:

  1. The Sparsity Gap: For sparse graphs ($m \approx n$), the $n^{1.5}$ work term remains dominant. Achieving near-linear work for all levels of graph sparsity in a parallel setting remains an open problem.
  2. The Polylogarithmic Goal: While $\sqrt{n}$ depth is a significant milestone, the ultimate goal in parallel computing is "NC" efficiency—achieving polylogarithmic depth while maintaining near-linear work. This remains the "holy grail" of parallel flow research.

Summary updated

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].
BibTeX
@inproceedings{brand2025parallel,
  author = {Jan van den Brand and Hossein Gholizadeh and Yonggang Jiang and Tijn de Vos},
  title = {{Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances}},
  booktitle = {SPAA},
  year = {2025},
  doi = {10.1145/3694906.3743356},
}
Figure