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

Abstract

We propose a randomized algorithm with query access that given a graph $G$ with arboricity $\hat{I}\pm$, and average degree $d$, makes $\tilde{O}\left(\frac{\hat{I}}{\pm }{\epsilon }^{2}d\right)$ \texttt{Degree} and $\tilde{O}\left(\frac{1}{{\epsilon }^2}\right)$ \texttt{Random Edge} queries to obtain an estimate $\hat{d}$ satisfying $\hat{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 \texttt{Degree}, \texttt{Neighbour}, and \texttt{Random 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 $\hat{I}\pm$, any algorithm that has access to \texttt{Degree}, \texttt{Neighbour}, and \texttt{Random Edge} queries, must make at least $\hat{I}\text{c◯}\left(\min \left(d,\frac{\hat{I}}{\pm }d\right)\right)$ queries to obtain a $(1\pm \epsilon )$-multiplicative estimate of $d$, even with the knowledge of $n$ and $\hat{I}\pm$. We also show that even with \texttt{Pair} and \texttt{FullNbr} queries, an algorithm must make $\hat{I}\text{c◯}\left(\min \left(d,\frac{\hat{I}}{\pm }d\right)\right)$ 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].

25 pages, 2 Figures