Assadi, Sepehr ;
Chakrabarty, Deeparnab ;
Khanna, Sanjeev
Graph Connectivity and Single Element Recovery via Linear and OR Queries
Abstract
We study the problem of finding a spanning forest in an undirected, nvertex multigraph 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 nonnegative 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 tradeoffs 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, rround algorithm which makes (N^{1/r}1)queries perround. We prove that this is tight: any rround deterministic algorithm must make ≥ (N^{1/r}  1) Linear queries in some round. In contrast, a 1round 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 rround deterministic algorithm in the ORmodel.
 We design a randomized, 2round algorithm for the graph connectivity problem which makes Õ(n)OR queries. In contrast, we prove that any 1round algorithm (possibly randomized) requires Ω̃(n²)OR queries. A randomized, 1round 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 (cutqueries) 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:17:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14588},
URN = {urn:nbn:de:0030drops145880},
doi = {10.4230/LIPIcs.ESA.2021.7},
annote = {Keywords: Query Models, Graph Connectivity, Group Testing, Duality}
}
31.08.2021
Keywords: 

Query Models, Graph Connectivity, Group Testing, Duality 
Seminar: 

29th Annual European Symposium on Algorithms (ESA 2021)

Issue date: 

2021 
Date of publication: 

31.08.2021 