Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs
Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai · 2021
We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For ≥ n^1+ε for any constant ε>0, our algorithm requires O(m łog n) work and O(łog^3 n) depth and succeeds with high probability. Its work matches the best O(m łog n) runtime for sequential algorithms [MN STOC'20; GMW SOSA'21]. This improves the previous best work by Geissmann and Gianinazzi [SPAA'18] by a O(łog^3 n) factor, while matching the depth of their algorithm. To do this, we design a work-efficient approximation algorithm and parallelize the recent sequential algorithms [MN STOC'21; GMW SOSA'21] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching.