期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-14
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 m is the number of edges in the graph and 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 is the number of vertices in the graph. Eden and Rosenbaum showed that Ω(m/t) many local queries are required for approximating the size of minimum cut in graphs. These two results together 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 ∈ N, Ω(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 ∈ N, Ω(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 query apart from local queries.
