License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.39
URN: urn:nbn:de:0030-drops-83168
Go to the corresponding LIPIcs Volume Portal

Rubinstein, Aviad ; Schramm, Tselil ; Weinberg, S. Matthew

Computing Exact Minimum Cuts Without Knowing the Graph

LIPIcs-ITCS-2018-39.pdf (0.6 MB)


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

BibTeX - Entry

  author =	{Aviad Rubinstein and Tselil Schramm and S. Matthew Weinberg},
  title =	{{Computing Exact Minimum Cuts Without Knowing the Graph}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Anna R. Karlin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-83168},
  doi =		{10.4230/LIPIcs.ITCS.2018.39},
  annote =	{Keywords: query complexity, minimum cut}

Keywords: query complexity, minimum cut
Collection: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Issue Date: 2018
Date of publication: 12.01.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI