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.

• An $O(m\frac{{\log }^{2}n}{\log \log n}+n{\log }^{6}n)$-time sequential algorithm: This improves Karger’s $O(m{\log }^{3}n)$ and $O(m\frac{(\log^2 n)\log (n^2/m)}{\log\log n} + n\log^6 n)$ bounds when the input graph is not extremely sparse or dense. Improvements over Karger’s bounds were previously known only under a rather strong assumption that the input graph is simple [Henzinger et al. SODA’17; Ghaffari et al. SODA’20]. For unweighted graphs with parallel edges, our bound can be improved to $O(m\frac{\log^{1.5} n}{\log\log n} + n\log^6 n)$.
• An algorithm requiring $\tilde{O}(n)$ cut queries to compute the min-cut of a weighted graph: This answers an open problem by Rubinstein et al. ITCS’18, who obtained a similar bound for simple graphs.
• A streaming algorithm that requires $\tilde{O}(n)$ space and $O(\log n)$ passes to compute the min-cut: The only previous non-trivial exact min-cut algorithm in this setting is the 2-pass $\tilde{O}(n)$-space algorithm on simple graphs [Rubinstein et al., ITCS’18] (observed by Assadi et al. STOC’19). In contrast to Karger’s 2-respecting min-cut algorithm which deploys sophisticated dynamic programming techniques, our approach exploits some cute structural properties so that it only needs to compute the values of $\tilde O(n)$cutscorrespondingtoremoving$\tilde O(n)$ pairs of tree edges, an operation that can be done quickly in many settings.