Computing exact minimum cuts without knowing the graph

Aviad Rubinstein, Tselil Schramm, Seth Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

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).

Original languageEnglish (US)
Title of host publication9th Innovations in Theoretical Computer Science, ITCS 2018
EditorsAnna R. Karlin
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770606
DOIs
StatePublished - Jan 1 2018
Event9th Innovations in Theoretical Computer Science, ITCS 2018 - Cambridge, United States
Duration: Jan 11 2018Jan 14 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume94
ISSN (Print)1868-8969

Other

Other9th Innovations in Theoretical Computer Science, ITCS 2018
CountryUnited States
CityCambridge
Period1/11/181/14/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Minimum cut
  • Query complexity

Cite this