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]