A Simple Semi-Streaming Algorithm for Global Minimum Cuts

Authors: Sepehr Assadi, Aditi Dudeja
Conference: The SIAM Symposium on Simplicity in Algorithms (SOSA@SODA'21)
Abstract: Recently, Rubinstein, Schramm, and Weinberg [ITCS’18] gave an algorithm for finding an exact global minimum cut of undirected graphs in the cut-query model in which the access to the graph is via querying the number of edges crossing a given cut. It was subsequently observed in the literature that this algorithm also implies that the minimum cut problem in the streaming model admits an ~O(n)-space algorithm in only two passes over the input.

In this note, we present a simpler and self-contained proof of this result in the streaming model with an improved space complexity that we show is within a sub-logarithmic factor of being optimal.
Conference version: [PDF]
BibTex: [DBLP]