Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size

We propose a randomized algorithm with query access that given a graph $G$ with arboricity $\alpha$, and average degree $d$, makes $\tilde{O}\left(\frac{\alpha }{{\epsilon }^{2}d}\right)$ $\mathtt{\text{Degree}}$ and $\tilde{O}\left(\frac{1}{{\epsilon }^2}\right)$ $\mathtt{\text{Random}}\mathtt{\text{Edge}}$ queries to obtain an estimate $\widehat{d}$ satisfying $\widehat{d}\in (1\pm \epsilon )d$. This improves the ${\tilde{O}}_{\epsilon ,\log n}\left(\sqrt{\frac{n}{d}}\right)$ query algorithm of [Beretta et al., SODA 2026] that has access to $\mathtt{\text{Degree}}$, $\mathtt{\text{Neighbour}}$, and $\mathtt{\text{Random}}\mathtt{\text{Edge}}$ queries. Our algorithm does not require any graph parameter as input, not even the size of the vertex set, and attains both simplicity and practicality through a new estimation technique. We complement our upper bounds with a lower bound that shows for all valid $n,d$, and $\alpha$, any algorithm that has access to $\mathtt{\text{Degree}}$, $\mathtt{\text{Neighbour}}$, and $\mathtt{\text{Random}}\mathtt{\text{Edge}}$ queries, must make at least $\mathrm{\Omega }(\min (d,\frac{\alpha }{d}))$ queries to obtain a $(1\pm \epsilon )$-multiplicative estimate of $d$, even with the knowledge of $n$ and $\alpha$. We also show that even with $\mathtt{\text{Pair}}$ and $\mathtt{\text{FullNbr}}$ queries, an algorithm must make $\mathrm{\Omega }(\min (d,\frac{\alpha }{d}))$ queries to obtain a $(1\pm \epsilon )$-multiplicative estimate of $d$. Our work addresses both the questions raised by the work of [Beretta et al., SODA 2026].