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 log 2 n log log n + n log 6 n -time sequential algorithm: This improves Karger's long-standing O(m log 3 n) and O m (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 (unweighted without parallel edges) [Henzinger, Rao, Wang, SODA'17; Ghaffari, Nowicki, Thorup, SODA'20]. For unweighted graphs (possibly with parallel edges) and using bit operations, our bound can be further improved to O m log 1.5 n log log n + n log 6 n .