Arboricity Matters in Triangle Counting with Random Edges

Abstract

Given a simple, unweighted, undirected graph $G=(V,E)$ with $|V|=n$ and $|E|=m$, and parameters $0<\epsilon ,\delta <1$, along with Degree, Neighbour, Pair and RandomEdge query access to $G$, we provide a query-based randomized algorithm to generate an estimate $\hat{T}$ of the number of triangles $T$ in $G$, such that $\hat{T}\in [(1-\epsilon )T,(1+\epsilon )T]$ with probability at least $1-\delta$. The query complexity of our algorithm is $\tilde{O}\left(m\alpha \log (1/\delta )/{\epsilon }^{3}T\right)$, where $\alpha$ is the arboricity of $G$. Our work can be seen as a natural progression to the line of recent works [Eden et al., SIAM J Comp., 2017; Assadi et al., ITCS 2019; Eden et al., SODA 2020] that considered subgraph or triangle counting with or without the use of RandomEdge query. Of these works, Eden et al. [SODA 2020] considers the role of arboricity. Our work is the first to consider how RandomEdge query can leverage the structural property of arboricity. Furthermore, continuing in the line of work of Assadi et al. [APPROX/RANDOM 2022], we also provide a lower bound of $\tilde{\Omega }\left(m\alpha \log (1/\delta )/{\epsilon }^{2}T\right)$ that matches the upper bound exactly on arboricity, $\delta$, and almost on $\epsilon$.

arXiv comment26 pages Appeared in RANDOM 2026