Nearly optimal edge estimation with independent set queries
Xi Chen, Amit Levi, Erik Waingarten · Society for Industrial and Applied Mathematics eBooks · 2019
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 ⊆ [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 + ϵ)-approximation of the number of edges m of the graph using · poly(log n, 1/ϵ) independent set queries. This improves the upper bound of · poly(log n, 1/ε) by Beame et al. [3]. Our second main result shows that /polylog(n) independent set queries are necessary, thus establishing that our algorithm is optimal up to a factor of poly(log n, 1/ϵ).