Parallel Minimum Cuts : An improved CREW PRAM algorithm

Abstract: This thesis considers the minimum cut problem in undirected, weighted graphs. We present a simple randomized CREW PRAM algorithm to find the minimum cut in a graph G with n nodes and m edges, based on Karger’s celebrated randomized near-linear time min-cut algorithm [STOC’96]. It has near-linear work O(m log2 n + n log6 n) and low depth O(log3 n), and returns the correct result with high probability. This is the first improvement to the best previous O(m log4 n) work and O(log3 n) depth CREW PRAM min-cut algorithm by Geissmann and Gianinazzi [SPAA’18]. For his randomized near-linear min-cut algorithm, Karger used a connection between minimum cuts and maximum packings of spanning trees to reduce the min-cut problem into two subproblems: (i) compute an approximate maximum tree packing S, and (ii) find the minimum cut of the graph G that cuts at most two edges from some tree in S—this is referred to as the 2-respecting min-cut problem. To achieve our main result, we give parallel algorithms for both subproblems. More precisely, we present the following.  An O(m log n + n log5 n) work and O(log2 n) depth CREW PRAM algorithm for the 2-respecting min-cut problem. This is obtained from parallelizing a recent sequential algorithm by Mukhopadhay and Nanongkai [STOC’20] that improves on Karger’s original result.  An O(m log2 n + n log4 n) work and O(log3 n) depth EREW PRAM algorithm to find an approximate maximum tree packing. This improves in a log n factor the work of the previously best known bound claimed by Karger [STOC’96] and used by Geissmann and Gianinazzi [SPAA’18].  In addition, we develop the following independent results:  A parallel implementation of the range tree data structure in two dimensions: given a set of n weighted points in the plane, it can be constructed using O(n log n) work and O(log2 n) depth on an EREW PRAM. In the CREW PRAM model, it supports the range counting, range reporting, and range sum queries work-optimally with O(log n) depth.  An O(log2 n+t log n)-time sequential algorithm to answer a 2-dimensional weighted range sampling query in a range tree on n weighted points. The query is defined as follows: given an integer t, sample t points independently from a query range, where each point is selected with probability proportional to its weight. In the CREW PRAM model, we show how to support this query work-optimally with O(log n) depth.