Graph Connectivity and Single Element Recovery via Linear and OR Queries
Authors:
Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna
Conference:
The European Symposium on Algorithms (ESA 2021)
Abstract:
We study the problem of finding a spanning forest in an undirected, n-vertex multi-graph under two basic query models. One are Linear queries which are linear measurements on the incidence vector
induced by the edges; the other are the weaker OR queries which only reveal whether a given subset
of plausible edges is empty or not. At the heart of our study lies a fundamental problem which we
call the single element recovery problem: given a non-negative vector x ∈ R^N_≥0
the objective is to return a single element x_j > 0 from the support. Queries can be made in rounds, and our goals is
to understand the trade-offs between the query complexity and the rounds of adaptivity needed to solve these problems, for both deterministic and randomized algorithms. These questions have
connections and ramifications to multiple areas such as sketching, streaming, graph reconstruction, and compressed sensing. Our main results are as follows:
All our algorithms, in fact, work with more natural graph query models which are special cases of the above, and have been extensively studied in the literature. These are Cross queries (cut-queries) and BIS (bipartite independent set) queries.
- For the single element recovery problem, it is easy to obtain a deterministic, r-round algorithm which makes (N^1/r-1)-queries per-round. We prove that this is tight: any r-round deterministic algorithm must make ≥ (N^1/r − 1) Linear queries in some round. In contrast, a 1-round O(polylog(N))-query randomized algorithm is known to exist.
- We design a deterministic O(r)-round, O˜(n^{1+1/r})-OR query algorithm for graph connectivity. We complement this with an Ω˜(n^{1+1/r})-lower bound for any r-round deterministic algorithm in the OR-model.
- We design a randomized, 2-round algorithm for the graph connectivity problem which makes O~(n)-OR queries. In contrast, we prove that any 1-round algorithm (possibly randomized) requires Ω(n^2)-OR queries. A randomized, 1-round algorithm making O~(n)-Linear queries is already known.
All our algorithms, in fact, work with more natural graph query models which are special cases of the above, and have been extensively studied in the literature. These are Cross queries (cut-queries) and BIS (bipartite independent set) queries.
Conference version:
[PDF]
Full version:
[arXiv]
BibTex:
[DBLP]