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
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8316/
Go to the corresponding LIPIcs Volume Portal

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

Computing Exact Minimum Cuts Without Knowing the Graph

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

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

BibTeX - Entry

@InProceedings{rubinstein_et_al:LIPIcs:2018:8316,
  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 =		{http://drops.dagstuhl.de/opus/volltexte/2018/8316},
  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