License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.6
URN: urn:nbn:de:0030-drops-146992
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14699/
Bishnu, Arijit ;
Ghosh, Arijit ;
Mishra, Gopinath ;
Paraashar, Manaswi
Query Complexity of Global Minimum Cut
Abstract
In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, where the graph can be accessed through local queries like Degree, Neighbor, and Adjacency queries.
Given ε ∈ (0,1), the algorithm with high probability outputs an estimate t̂ satisfying the following (1-ε) t ≤ t̂ ≤ (1+ε) t, where t is the size of minimum cut in the graph. The expected number of local queries used by our algorithm is min{m+n,m/t}poly(log n,1/(ε)) where n and m are the number of vertices and edges in the graph, respectively. Eden and Rosenbaum showed that Ω(m/t) local queries are required for approximating the size of minimum cut in graphs, {but no local query based algorithm was known. Our algorithmic result coupled with the lower bound of Eden and Rosenbaum [APPROX 2018] resolve the query complexity of the problem of estimating the size of minimum cut in graphs using local queries.}
Building on the lower bound of Eden and Rosenbaum, we show that, for all t ∈ ℕ, Ω(m) local queries are required to decide if the size of the minimum cut in the graph is t or t-2. Also, we show that, for any t ∈ ℕ, Ω(m) local queries are required to find all the minimum cut edges even if it is promised that the input graph has a minimum cut of size t. Both of our lower bound results are randomized, and hold even if we can make Random Edge queries in addition to local queries.
BibTeX - Entry
@InProceedings{bishnu_et_al:LIPIcs.APPROX/RANDOM.2021.6,
author = {Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath and Paraashar, Manaswi},
title = {{Query Complexity of Global Minimum Cut}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {6:1--6:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-207-5},
ISSN = {1868-8969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14699},
URN = {urn:nbn:de:0030-drops-146992},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.6},
annote = {Keywords: Query complexity, Global mincut}
}
|
Keywords: |
|
Query complexity, Global mincut |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
15.09.2021 |
