From Decision to Random Certificates: Exponential Separation for Edge Estimation with Independent Set Queries

Abstract

We study the problem of estimating the number of edges in an undirected, unweighted graph using sublinear query access. We consider a query model that preserves the structure of Independent Set (IS) queries, but augments their output with a random certificate: given a vertex subset, the oracle returns a uniformly random edge from the induced subgraph if one exists, and returns null otherwise. Using this access, we give a randomized algorithm that outputs a $(1 \pm \varepsilon)$-approximation to the number of edges with constant success probability using $\widetilde{O}(\log^{2} m)$ queries. This implies an exponential separation from both standard IS queries and global random edge-sampling models: estimating the number of edges using standard IS queries require $\widetilde{\Theta}\!\left(\min\left\{\sqrt{m},\, \frac{n}{\sqrt{m}}\right\}\right)$ queries, while direct random edge-sample access requires $\widetilde{\Theta}(\sqrt{m})$ samples. Beyond separation in query complexity, our algorithm is output-sensitive: its query complexity is polylogarithmic in the number of edges in the graph. This aligns with the classical objective in group testing, where one seeks algorithms that are both worst-case optimal and instance-adaptive. Conceptually, our model connects group testing, the decision-versus-counting dichotomy, graph property testing, and the"power of a random certificate", and can be viewed as a structured form of conditional sampling of edges in graphs.