@inproceedings{4fbd155c3c0d4063ad6d0be744be10d7,
title = "Computing exact minimum cuts without knowing the graph",
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 ⊂ 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(n5/3) queries, and computing an exact global minimum cut of G with only O(n) queries (while learning the graph requires (n2) queries).",
keywords = "Minimum cut, Query complexity",
author = "Aviad Rubinstein and Tselil Schramm and Weinberg, {S. Matthew}",
note = "Funding Information: A. Rubinstein did most of the work while at UC Berkeley and a visitor at the Simons Institute for the Theory of Computing, supported by a Microsoft PhD Fellowship, as well as a Rabin Postdoctoral Fellowship, NSF grant CCF1408635, and Templeton Foundation grant 3966. † T. Schramm is grateful for the support of an NSF Graduate Research Fellowship (1106400). ‡ S. M. Weinberg is grateful for support from NSF CCF-1717899. This work was completed in part while S. M. Weinberg was a research fellow at the Simons Institute for the Theory of Computing. Funding Information: A. Rubinstein did most of the work while at UC Berkeley and a visitor at the Simons Institute for the Theory of Computing, supported by a Microsoft PhD Fellowship, as well as a Rabin Postdoctoral Fellowship, NSF grant CCF1408635, and Templeton Foundation grant 3966. ? T. Schramm is grateful for the support of an NSF Graduate Research Fellowship (1106400). ? S. M. Weinberg is grateful for support from NSF CCF-1717899. This work was completed in part while S. M. Weinberg was a research fellow at the Simons Institute for the Theory of Computing. Publisher Copyright: {\textcopyright} Aviad Rubinstein and Tselil Schramm and S. Matthew Weinberg.; 9th Innovations in Theoretical Computer Science, ITCS 2018 ; Conference date: 11-01-2018 Through 14-01-2018",
year = "2018",
month = jan,
day = "1",
doi = "10.4230/LIPIcs.ITCS.2018.39",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Karlin, {Anna R.}",
booktitle = "9th Innovations in Theoretical Computer Science, ITCS 2018",
address = "Germany",
}