Graph algorithm

It has been observed independently by many researchers that the isolating cut lemma of Li and Panigrahi [FOCS 2020] can be easily extended to obtain new algorithms for finding the non-trivial minimizer of a symmetric submodular function and solving the hypergraph minimum cut problem. This note contains these observations.

We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $m\ge n^{1+ϵ}$ for any constant $ϵ>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.

Minimum-weight cut (min-cut) is a basic measure of a network's connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC'96], there was no efficient way for a distributed network to compute its own min-cut without limiting the input structure or dropping the output quality: In the standard CONGEST model, existing algorithms with nearly-optimal time (e.g. [Ghaffari, Kuhn, DISC'13; Nanongkai, Su, DISC'14]) can guarantee a solution that is $(1+ϵ)$-approximation at best while the exact $\tilde O(n^{0.

Consider the following 2-respecting min-cut problem. Given a weighted graph $G$ and its spanning tree $T$, find the minimum cut among the cuts that contain at most two edges in $T$. This problem is an important subroutine in Karger's celebrated randomized near-linear-time min-cut algorithm [STOC'96]. We present a new approach for this problem which can be easily implemented in many settings, leading to the following randomized min-cut algorithms for weighted graphs.