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

TL;DR

This paper presents a breakthrough randomized parallel algorithm for the Minimum Cost Flow problem that achieves near-linear work and square-root depth for dense graphs. By developing a novel dynamic parallel expander decomposition, the authors bridge a long-standing gap in parallel graph algorithms, matching or exceeding the state-of-the-art for max flow, bipartite matching, and shortest paths.

What Problem Does This Paper Address?

The Minimum Cost Flow (min-cost flow) problem is a cornerstone of combinatorial optimization: given a graph with costs and capacities on its edges, find the cheapest way to send a specific amount of flow from sources to sinks.

In the world of parallel computing, we evaluate algorithms using two metrics:

  1. Work: The total number of operations performed (ideally close to the best sequential algorithm).
  2. Depth: The longest chain of dependent operations (representing the time taken if we had infinite processors).

For decades, researchers faced a trade-off: algorithms were either "work-efficient" but highly sequential (high depth), or "fast" (low depth) but extremely wasteful in terms of total work. While recent breakthroughs achieved near-linear work for sequential flow, parallelizing these techniques remained a major challenge, particularly for the general min-cost flow problem.

Methods

The authors build their solution on a modern Interior Point Method (IPM) framework. IPMs solve optimization problems by following a "central path" through the interior of the feasible region using iterative Newton steps.

The core technical contribution is the parallelization of the data structures required for each IPM iteration. Specifically:

  • Dynamic Parallel Expander Decomposition: To efficiently sample edges and maintain "Lewis weights" (a way of measuring edge importance), the algorithm needs to partition the graph into "expanders"—subgraphs that are well-connected and lack bottlenecks. Previous methods for maintaining these decompositions under edge deletions were highly sequential. The authors adapt recent work on static parallel expanders to create a dynamic version that supports low-depth updates.
  • Parallel Data Structure Maintenance: They parallelize the maintenance of the primal solution, gradients, and dual variables. Most of these involve matrix-vector products and sketching techniques that are naturally suited for parallel execution once the underlying graph partition (the expander decomposition) is stable.
  • Push-Relabel Subroutines: They use a parallel version of the push-relabel algorithm to find "certificates" that prove a subgraph is an expander or identify where it needs to be pruned.

Datasets

As a theoretical contribution to computer science, this paper does not use empirical datasets or benchmarks. Instead, it provides a rigorous mathematical analysis of the algorithm's complexity on general $n$-vertex, $m$-edge directed graphs with polynomially bounded integer costs and capacities.

Key Insights and Ideas

  • The Density Sweet Spot: The authors identify that for "moderately dense" graphs (where the number of edges $m$ is at least $n^{1.5}$), they can achieve near-linear work ($O(m)$) while keeping depth at $\tilde{O}(\sqrt{n})$.
  • Expander Pruning as the Bottleneck: They pinpointed that the primary obstacle to parallelizing state-of-the-art flow algorithms was the sequential nature of expander pruning. By solving this, they unlocked parallel speedups for the entire IPM.
  • Implicit Maintenance: The algorithm doesn't explicitly update every variable in every round. Instead, it uses a "heavy hitter" approach to only update entries that have changed significantly, which is crucial for maintaining work efficiency.
  • Improving Special Cases: Because min-cost flow is a general problem, this result automatically improves parallel bounds for bipartite matching, reachability, and shortest paths, notably removing a small $n^{o(1)}$ factor that plagued previous "near-optimal" algorithms.

Key Results

  • Complexity: The algorithm achieves $O(m + n^{1.5})$ work and $\tilde{O}(\sqrt{n})$ depth.
  • Dense Graph Performance: For graphs where $m > n^{1.5}$, this is the first algorithm to achieve both near-linear work and sub-linear depth.
  • Comparison to State-of-the-Art:
    • It improves upon the landmark work of Lee and Sidford (2014), which required $O(m\sqrt{n})$ work for the same depth.
  • For Shortest Paths and Reachability, it improves the depth from $n^{0.5+o(1)}$ to a clean $\tilde{O}(\sqrt{n})$ for dense instances.

Limitations and Future Work

  • Sparsity Gap: The algorithm's work efficiency is best on dense graphs. For very sparse graphs ($m \approx n$), the $n^{1.5}$ term in the work complexity becomes dominant, meaning it is not yet "near-linear work" for all graph types.
  • Randomization: The algorithm is randomized and succeeds with high probability. A deterministic version with similar bounds remains an open challenge.
  • Depth Floor: The $\sqrt{n}$ depth is a common barrier in flow algorithms. Achieving "polylogarithmic" depth (extremely fast parallelization) while maintaining linear work remains the "holy grail" of this field.

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},
}

Loading related content...

Figure