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.