Parallel Minimum Cuts in Near-linear Work and Low Depth

Understand

We present the first near-linear work and poly-logarithmic depth algorithm for computing a minimum cut in a graph, while previous parallel algorithms with poly-logarithmic depth required at least quadratic work in the number of vertices.

• In a graph with $n$ vertices and $m$ edges, our algorithm computes the correct result with high probability in $O(m {\log}^4 n)$ work and $O({\log}^3 n)$ depth.
• This result is obtained by parallelizing a data structure that aggregates weights along paths in a tree and by exploiting the connection between minimum cuts and approximate maximum packings of spanning trees.
• In addition, our algorithm improves upon bounds on the number of cache misses incurred to compute a minimum cut.