Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the query complexity of connectivity with global queries
380
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 query a vector $x in {0,1}^n$ and receive the answer $Ax$. We give a randomized algorithm that can output a spanning forest of a weighted graph with constant probability after $O(log^4(n))$ matrix-vector multiplication queries to the adjacency matrix. This complements a result of Sun et al. (ICALP 2019) that gives a randomized algorithm that can output a spanning forest of a graph after $O(log^4(n))$ matrix-vector multiplication queries to the signed vertex-edge incidence matrix of the graph. As an application, we show that a quantum algorithm can output a spanning forest of an unweighted graph after $O(log^5(n))$ cut queries, improving and simplifying a result of Lee, Santha, and Zhang (SODA 2021), which gave the bound $O(log^8(n))$. In the second part of the paper, we turn to showing lower bounds on the linear query complexity of determining if a graph is connected. If $w$ is the weight vector of a graph (viewed as an $binom{n}{2}$ dimensional vector), in a linear query one can query any vector $z in mathbb{R}^{n choose 2}$ and receive the answer $langle z, wrangle$. We show that a zero-error randomized algorithm must make $Omega(n)$ linear queries in expectation to solve connectivity. As far as we are aware, this is the first lower bound of any kind on the unrestricted linear query complexity of connectivity. We show this lower bound by looking at the linear query emph{certificate complexity} of connectivity, and characterize this certificate complexity in a linear algebraic fashion.
rate research
Read More
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 investigate the parameterized complexity in $a$ and $b$ of determining whether a graph~$G$ has a subset of $a$ vertices and $b$ edges whose removal disconnects $G$, or disconnects two prescribed vertices $s, t in V(G)$.
Let $G$ be an $n$-vertex graph with $m$ edges. When asked a subset $S$ of vertices, a cut query on $G$ returns the number of edges of $G$ that have exactly one endpoint in $S$. We show that there is a bounded-error quantum algorithm that determines all connected components of $G$ after making $O(log(n)^6)$ many cut queries. In contrast, it follows from results in communication complexity that any randomized algorithm even just to decide whether the graph is connected or not must make at least $Omega(n/log(n))$ many cut queries. We further show that with $O(log(n)^8)$ many cut queries a quantum algorithm can with high probability output a spanning forest for $G$. En route to proving these results, we design quantum algorithms for learning a graph using cut queries. We show that a quantum algorithm can learn a graph with maximum degree $d$ after $O(d log(n)^2)$ many cut queries, and can learn a general graph with $O(sqrt{m} log(n)^{3/2})$ many cut queries. These two upper bounds are tight up to the poly-logarithmic factors, and compare to $Omega(dn)$ and $Omega(m/log(n))$ lower bounds on the number of cut queries needed by a randomized algorithm for the same problems, respectively. The key ingredients in our results are the Bernstein-Vazirani algorithm, approximate counting with OR queries, and learning sparse vectors from inner products as in compressed sensing.
Cognitive Radio Networks (CRNs) are considered as a promising solution to the spectrum shortage problem in wireless communication. In this paper, we initiate the first systematic study on the algorithmic complexity of the connectivity problem in CRNs through spectrum assignments. We model the network of secondary users (SUs) as a potential graph, where two nodes having an edge between them are connected as long as they choose a common available channel. In the general case, where the potential graph is arbitrary and the SUs may have different number of antennae, we prove that it is NP-complete to determine whether the network is connectable even if there are only two channels. For the special case where the number of channels is constant and all the SUs have the same number of antennae, which is more than one but less than the number of channels, the problem is also NP-complete. For the special cases in which the potential graph is complete, a tree, or a graph with bounded treewidth, we prove the problem is NP-complete and fixed-parameter tractable (FPT) when parameterized by the number of channels. Exact algorithms are also derived to determine the connectability of a given cognitive radio network.
State complexity of quantum finite automata is one of the interesting topics in studying the power of quantum finite automata. It is therefore of importance to develop general methods how to show state succinctness results for quantum finite automata. One such method is presented and demonstrated in this paper. In particular, we show that state succinctness results can be derived out of query complexity results.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
