2019/07/09 by Xi Chen, Chen, Xi, Amit Levi +3 · 3 citations
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1907.04381
openalex publication_date 2019/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 min(√(m),n / √(m))⋅\textrmpoly(log n,1/ε) independent set queries. This improves the upper bound of min(√(m),n2/m)⋅\textrmpoly(log n,1/ε) by Beame et al. \citeBHRRS18. Our second main result shows that min(√(m),n/√(m)))/\textrmpolylog(n) independent set queries are necessary, thus establishing that our algorithm is optimal up to a factor of \textrmpoly(log n, 1/ε).