{"ID":2845892,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.03650","arxiv_id":"2511.03650","title":"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 $α$, and average degree $d$, makes $\\widetilde{O}\\left(\\fracα{\\varepsilon^2d}\\right)$ \\texttt{Degree} and $\\widetilde{O}\\left(\\frac{1}{\\varepsilon^2}\\right)$ \\texttt{Random Edge} queries to obtain an estimate $\\widehat{d}$ satisfying $\\widehat{d} \\in (1\\pm\\varepsilon)d$. This improves the $\\widetilde{O}_{\\varepsilon,\\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 $α$, any algorithm that has access to \\texttt{Degree}, \\texttt{Neighbour}, and \\texttt{Random Edge} queries, must make at least $Ω\\left(\\min\\left(d,\\fracα{d}\\right)\\right)$ queries to obtain a $(1\\pm\\varepsilon)$-multiplicative estimate of $d$, even with the knowledge of $n$ and $α$. We also show that even with \\texttt{Pair} and \\texttt{FullNbr} queries, an algorithm must make $Ω\\left(\\min\\left(d,\\fracα{d}\\right)\\right)$ queries to obtain a $(1\\pm\\varepsilon)$-multiplicative estimate of $d$. Our work addresses both the questions raised by the work of [Beretta et al., SODA 2026].","short_abstract":"We propose a randomized algorithm with query access that given a graph $G$ with arboricity $α$, and average degree $d$, makes $\\widetilde{O}\\left(\\fracα{\\varepsilon^2d}\\right)$ \\texttt{Degree} and $\\widetilde{O}\\left(\\frac{1}{\\varepsilon^2}\\right)$ \\texttt{Random Edge} queries to obtain an estimate $\\widehat{d}$ satisf...","url_abs":"https://arxiv.org/abs/2511.03650","url_pdf":"https://arxiv.org/pdf/2511.03650v1","authors":"[\"Debarshi Chanda\"]","published":"2025-11-05T17:08:23Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}