Computing exact minimum cuts without knowing the graph

We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimization problem: on query S subset V, the oracle returns the size of the cut between S and V setminus S. We provide algorithms computing an exact minimum s-t cut in G with tildeO(n5/3) queries, and computing an exact global minimum cut of G with only tildeO(n) queries (while learning the graph requires tildeTheta(n2) queries).