Nearly optimal edge estimation with independent set queries

Abstract

We study the problem of estimating the number of edges of an unknown, undirected graph $G=([n],E)$ with access to an independent set oracle. When queried about a subset $S\subseteq [n]$ of vertices the independent set oracle answers whether $S$ is an independent set in $G$ or not. Our first main result is an algorithm that computes a $(1+\epsilon )$-approximation of the number of edges $m$ of the graph using $\min (\sqrt{m},n/\sqrt{m})\cdot \text{poly}(\log n,1/\epsilon )$ independent set queries. This improves the upper bound of $\min (\sqrt{m},n^2/m)\cdot \text{poly}(\log n,1/\epsilon )$ by Beame et al. \cite{BHRRS18}. Our second main result shows that $\min (\sqrt{m},n/\sqrt{m}))/\text{polylog}(n)$ independent set queries are necessary, thus establishing that our algorithm is optimal up to a factor of $\text{poly}(\log n,1/\epsilon )$.

Cited by in corpus (1)

• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems