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 t2. 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:16:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14699},
URN = {urn:nbn:de:0030drops146992},
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 