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 Kargers celebrated randomized near-linear-time min-cut algorithm [STOC96]. 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(mfrac{log^2 n}{loglog n} + nlog^6 n)$-time sequential algorithm: This improves Kargers $O(m log^3 n)$ and $O(mfrac{(log^2 n)log (n^2/m)}{loglog n} + nlog^6 n)$ bounds when the input graph is not extremely sparse or dense. Improvements over Kargers bounds were previously known only under a rather strong assumption that the input graph is simple [Henzinger et al. SODA17; Ghaffari et al. SODA20]. For unweighted graphs with parallel edges, our bound can be improved to $O(mfrac{log^{1.5} n}{loglog n} + nlog^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. ITCS18, 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., ITCS18] (observed by Assadi et al. STOC19). In contrast to Kargers 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)$ cuts corresponding to removing $tilde O(n)$ pairs of tree edges, an operation that can be done quickly in many settings.