Finance
November 2017
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⊂V, the oracle returns the size of the cut between S and V∖S.
We provide algorithms computing an exact minimum s-t cut in G with Õ (n5/3) queries, and computing an exact global minimum cut of G with only Õ (n) queries (while learning the graph requires Θ̃ (n2) queries).