License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.7
URN: urn:nbn:de:0030-drops-145880
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14588/
Go to the corresponding LIPIcs Volume Portal

Assadi, Sepehr ; Chakrabarty, Deeparnab ; Khanna, Sanjeev

Graph Connectivity and Single Element Recovery via Linear and OR Queries

pdf-format:
LIPIcs-ESA-2021-7.pdf (0.8 MB)

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 ∈ ℝ^{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:
- 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)-query randomized algorithm is known to exist.
- We design a deterministic O(r)-round, Õ(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 Õ(n)-OR queries. In contrast, we prove that any 1-round algorithm (possibly randomized) requires Ω̃(n²)-OR queries. A randomized, 1-round algorithm making Õ(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.

BibTeX - Entry

@InProceedings{assadi_et_al:LIPIcs.ESA.2021.7,
  author =	{Assadi, Sepehr and Chakrabarty, Deeparnab and Khanna, Sanjeev},
  title =	{{Graph Connectivity and Single Element Recovery via Linear and OR Queries}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14588},
  URN =		{urn:nbn:de:0030-drops-145880},
  doi =		{10.4230/LIPIcs.ESA.2021.7},
  annote =	{Keywords: Query Models, Graph Connectivity, Group Testing, Duality}
}

Keywords: Query Models, Graph Connectivity, Group Testing, Duality
Collection: 29th Annual European Symposium on Algorithms (ESA 2021)
Issue Date: 2021
Date of publication: 31.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI