Parallel Minimum Cuts in Near-linear Work and Low Depth

Barbara Geissmann, Lukas Gianinazzi

Researchers from ETH Zurich have achieved a significant milestone in parallel graph algorithms by developing a method to find the minimum cut of a graph using near-linear total work and very low depth (parallel time). This breakthrough bridges the gap between highly efficient sequential algorithms and scalable parallel implementations.

The Minimum Cut Problem

The minimum cut problem involves finding the smallest set of edges that, when removed, partition a graph into two disconnected components. This is a fundamental problem in network reliability, cluster analysis, and community detection.

A simple example of a graph cut partitioning nodes into two sets.

Historically, parallelizing min-cut algorithms has involved a difficult trade-off:

  1. Low-depth algorithms could finish quickly using many processors but were "work-inefficient," often requiring quadratic work ($O(n^2)$).
  2. Work-efficient algorithms often contained sequential bottlenecks (high depth) that prevented them from scaling on massive parallel systems.

Technical Innovation: Parallelizing Tree Operations

The authors build upon Karger’s algorithm, which utilizes "tree packing" to find a set of spanning trees. Karger demonstrated that the minimum cut of a graph will likely cut at most two edges of at least one of these spanning trees. The core innovation of this paper is a parallel version of a Minimum Path data structure designed to handle these constraints efficiently.

Visualizing the MinPath and AddPath operations on the tree-based data structure.

Key Technical Moves:

  • Batching instead of Streaming: Unlike standard data structures that process updates sequentially, this algorithm processes all updates and queries in a massive "batch" using parallel sorting and prefix sums.
  • Bough Decomposition: The spanning tree is decomposed into vertex-disjoint paths called "boughs." This transforms complex tree operations into simpler prefix operations on lists, which are easier to parallelize.
  • Telescoping States: To avoid sequential bottlenecks when updating nodes, the authors show that node states can be calculated as telescoping sums. This allows for the use of parallel prefix sum approaches to compute all intermediate states simultaneously.

Key Results and Complexity

The resulting algorithm achieves $O(m \log^4 n)$ work and $O(\log^3 n)$ depth. For sparse graphs, this represents a massive improvement over previous polylogarithmic-depth algorithms that required $\Theta(n^2 \log n)$ work.

Beyond theoretical complexity, the algorithm is highly cache-efficient. It incurs $O(\lceil (m \log^4 n)/B \rceil)$ cache misses, outperforming previous state-of-the-art results by a factor of $\Theta(\log n / \log_M n)$. Because the overhead compared to sequential versions is only logarithmic, the algorithm is theoretically viable for large-scale shared-memory systems.

Limitations and Future Work

While the algorithm is near-linear, it is not yet truly work-optimal, as it performs $O(\log n)$ more work than the best known sequential algorithm ($O(m \log^3 n)$). Additionally, the overall depth is currently limited by the initial step of finding spanning trees; if faster spanning tree algorithms are developed, the "Minimum Path" component is already fast enough to support even lower total depth. Finally, as a Monte Carlo algorithm, it returns the correct result with high probability; finding a deterministic parallel algorithm with similar bounds remains a major open challenge in the field.

Summary updated

BibTeX
@article{geissmann2018parallel,
  author = {Barbara Geissmann and Lukas Gianinazzi},
  title = {{Parallel Minimum Cuts in Near-linear Work and Low Depth}},
  journal = {ACM Trans. Parallel Comput.},
  year = {2018},
  doi = {10.1145/3460890},
}
Figure