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 tree-packing approach. It has near-linear work \(O(m \log^2 n + n \log^6 n)\) and low depth \(O(\log^3 n)\), and returns the correct result with high probability. This is the first improvement to the best previous \(O(m \log^4 n)\) work and \(O(\log^3 n)\) depth CREW PRAM min-cut algorithm by Geissmann and Gianinazzi. For his randomized near-linear min-cut algorithm Karger used a connection between minimum cuts and maximum packings of spanning trees to reduce the minimum cut problem into two subproblems: (i) compute an approximate maximum tree packing \(\mathcal{S}\), and (ii) find the minimum cut of the graph \(G\) that cuts at most two edges from some tree in \(\mathcal{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 \log^5 n)\) work and \(O(\log^2 n)\) depth CREW PRAM algorithm for the 2-respecting min-cut problem. This was obtained by parallelizing a recent sequential algorithm by Mukhopadhay and Nanongkai that improves on Karger’s original result.
An \(O(m \log^2 n + n \log^4 n)\) work and \(O(\log^3 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 bounds claimed by Karger, and used by Geissmann and Gianinazzi for their parallel min-cut algorithm.
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(\log^2 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(\log^2 n + t \log n)\)-time sequential algorithm to answer 2-dimensional weighted range sampling queries 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.