ﻻ يوجد ملخص باللغة العربية
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}right}mbox{poly}left(log n,frac{1}{epsilon}right)$ 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.
We study the query complexity of determining if a graph is connected with global queries. The first model we look at is matrix-vector multiplication queries to the adjacency matrix. Here, for an $n$-vertex graph with adjacency matrix $A$, one can que
The minimum cut problem in an undirected and weighted graph $G$ is to find the minimum total weight of a set of edges whose removal disconnects $G$. We completely characterize the quantum query and time complexity of the minimum cut problem in the ad
Consider the following 2-respecting min-cut problem. Given a weighted graph $G$ and its spanning tree $T$, find the minimum cut among the cuts that contain at most two edges in $T$. This problem is an important subroutine in Kargers celebrated random
We present a practically efficient algorithm for maintaining a global minimum cut in large dynamic graphs under both edge insertions and deletions. While there has been theoretical work on this problem, our algorithm is the first implementation of a
Minimum Label Cut (or Hedge Connectivity) problem is defined as follows: given an undirected graph $G=(V, E)$ with $n$ vertices and $m$ edges, in which, each edge is labeled (with one or multiple labels) from a label set $L={ell_1,ell_2, ..., ell_{|L