@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 = "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",
}