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(mfraclog2 nloglog n + nlog6 n)-time sequential algorithm: This improves Karger's O(m log3 n) and O(mfrac(log2 n)log (n2/m)loglog n + nlog6 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(mfraclog1.5 nloglog n + nlog6 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) cuts corresponding to removing tilde O(n) pairs of tree edges, an operation that can be done quickly in many settings.