Computing Exact Minimum Cuts Without Knowing the Graph
Andrei Graura b, Tristan Pollnera c, Ramaswamy, Vidhyad e, Seth Matthew Weinbergd
- aDepartment of Mathematics, Princeton University, Princeton, NJ, USA
- bHarvard University, Cambridge, United States
- cUniversity of California, Berkeley, Berkeley, United States
- dDepartment of Computer Science, Princeton University, Princeton, NJ, USA
- ePrinceton University, Princeton, United States
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
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 \ S. We provide algorithms computing an exact minimum $s$-$t$ cut in $G$ with ~{O}(n^{5/3}) queries, and computing an exact global minimum cut of G with only ~{O}(n) queries (while learning the graph requires ~{\Theta}(n^2) queries).
TL;DRThis work provides query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs, inspired by the submodular function minimization problem. (Semantic Scholar)