Min-cut

Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition

We design an algorithm for computing connectivity in hypergraphs which runs in time $\hat O_r(p + \min{\lambda n^2, n^r/\lambda})$, where $p$ is the size, $n$ is the number of vertices, $r$ is the rank (size of the largest hyperedge), and $\lambda$ is the connectivity of the hypergraph. The $\hat O_r(\cdot)$ hides terms that are subpolynomial in the main parameter and terms that depend only on $r$. Our algorithm is faster than existing algorithms when the connectivity $\lambda$ is $\Omega(n^{(r-2)/2})$.

Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs

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.

Distributed Weighted Min-Cut in Nearly-Optimal Time

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+\epsilon)$-approximation at best while the exact $\tilde O(n^{0.

Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms

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.