Parallel Minimum Cuts in O(m log² n) Work and Low Depth

We present a randomized O(m log(2) n) work, O( polylogn) depth parallel algorithm for minimum cut. This algorithm matches thework bounds of a recent sequential algorithm by Gawrychowski, Mozes, andWeimann [ICALP'20], and improves on the previously best parallel algorithm by Geissmann and Gianinazzi [SPAA'18], which performs O(m log(4) n) work in O(polylogn) depth. Our algorithm makes use of three components that might be of independent interest. First, we design a parallel data structure that efficiently supports batched mixed queries and updates on trees. It generalizes and improves thework bounds of a previous data structure of Geissmann and Gianinazzi and iswork efficient with respect to the best sequential algorithm. Second, we design a parallel algorithm for approximate minimum cut that improves on previous results by Karger and Motwani. We use this algorithm to give a work-efficient procedure to produce a tree packing, as in Karger's sequential algorithm for minimum cuts. Last, we design an efficient parallel algorithm for solving the minimum 2-respecting cut problem.