2026-07-21T19:38:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14699 2024-03-06T10:54:41Z ddc:004 open_access

Query Complexity of Global Minimum Cut Bishnu, Arijit Ghosh, Arijit Mishra, Gopinath Paraashar, Manaswi Query complexity Global mincut 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arijit Bishnu and Arijit Ghosh and Gopinath Mishra and Manaswi Paraashar 2021 Is Part Of LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2021.6 urn:nbn:de:0030-drops-146992 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.6 eng https://creativecommons.org/licenses/by/4.0/legalcode