We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $m\geq n^{1+\epsilon}$ for any constant $\epsilon>0$, our algorithm requires $O(m \log n)$ work and $O(\log^3 n)$ depth and succeeds with high probability. Its work matches the best $O(m \log n)$ runtime for sequential algorithms [MN STOCâ€™20; GMW SOSA’21]. This improves the previous best work by Geissmann and Gianinazzi [SPAA’18] by $O(\log^3 n)$ factor, while matching the depth of their algorithm.

Powered by the Academic theme for Hugo.