Query Complexity of Global Minimum Cut
Query Complexity of Global Minimum Cut
复制标题
全局最小割的查询复杂度
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Manaswi Paraashar
中科院分区：
文献类型：
--
作者：
Arijit Bishnu;Arijit Ghosh;Gopinath Mishra;Manaswi Paraashar
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 {sc Degree}, {sc Neighbor}, and {sc Adjacency} queries.
Given $epsilon in (0,1)$, the algorithm with high probability outputs an estimate $hat{t}$ satisfying the following $(1-epsilon) t leq hat{t} leq (1+epsilon) 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 $minleft{m+n,frac{m}{t}
ight}mbox{poly}left(log n,frac{1}{epsilon}
ight)$ where $n$ is the number of vertices in the graph. Eden and Rosenbaum showed that $Omega(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 in mathbb{N}$, $Omega(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 in mathbb{N}$, $Omega(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 {sc Random Edge} query apart from local queries.
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 {sc Degree}, {sc Neighbor}, and {sc Adjacency} queries.
Given $epsilon in (0,1)$, the algorithm with high probability outputs an estimate $hat{t}$ satisfying the following $(1-epsilon) t leq hat{t} leq (1+epsilon) 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 $minleft{m+n,frac{m}{t}
ight}mbox{poly}left(log n,frac{1}{epsilon}
ight)$ where $n$ is the number of vertices in the graph. Eden and Rosenbaum showed that $Omega(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 in mathbb{N}$, $Omega(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 in mathbb{N}$, $Omega(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 {sc Random Edge} query apart from local queries.
通过边缘采样计算星子图的次线性时间算法
影响因子：
1.1
作者：
Aliakbarpour, Maryam;Biswas, Amartya Shankha;Gouleakis, Themis;Peebles, John;Rubinfeld, Ronitt;Yodpinyanee, Anak
通讯作者：
Yodpinyanee, Anak