Graph connectivity and single element recovery via linear and OR queries

Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


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 ∈ RN0, the objective is to return a single element xj > 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: For the single element recovery problem, it is easy to obtain a deterministic, r-round algorithm which makes (N1/r−1)-queries per-round. We prove that this is tight: any r-round deterministic algorithm must make ≥ (N1/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, Õ(n1+1/r)-OR query algorithm for graph connectivity. We complement this with an Ω(~ n1+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 Oe(n)-OR queries. In contrast, we prove that any 1-round algorithm (possibly randomized) requires Ω(e n2)-OR queries. A randomized, 1-round algorithm making Oe(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.

Original languageEnglish (US)
Title of host publication29th Annual European Symposium on Algorithms, ESA 2021
EditorsPetra Mutzel, Rasmus Pagh, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772044
StatePublished - Sep 1 2021
Event29th Annual European Symposium on Algorithms, ESA 2021 - Vitual, Lisbon, Portugal
Duration: Sep 6 2021Sep 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference29th Annual European Symposium on Algorithms, ESA 2021
CityVitual, Lisbon

All Science Journal Classification (ASJC) codes

  • Software


  • Duality
  • Graph connectivity
  • Group testing
  • Query models


Dive into the research topics of 'Graph connectivity and single element recovery via linear and OR queries'. Together they form a unique fingerprint.

Cite this