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:
- Work: The total number of operations (ideally matching the best sequential algorithm).
- 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:
- 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.
- 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