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: https://drops.dagstuhl.de/opus/volltexte/2021/14699/
 Go to the corresponding LIPIcs Volume Portal

### Query Complexity of Global Minimum Cut

 pdf-format:

### 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

DROPS-Home | Fulltext Search | Imprint | Privacy