2021/02/12 by López-Martínez, Andrés, Mukhopadhyay, Sagnik, Nanongkai, Danupon
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2102.06565
We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For m≥ n1+ε for any constant ε>0, our algorithm requires O(m log n) work and O(log3 n) depth and succeeds with high probability. Its work matches the best O(m log n) runtime for sequential algorithms [MN STOC 2020, GMW SOSA 2021]. This improves the previous best work by Geissmann and Gianinazzi [SPAA 2018] by O(log3 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 2020; GMW SOSA 2021] that exploit a connection between 2-respecting minimum cuts and 2-dimensional orthogonal range searching.