Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries

Given a simple, unweighted, undirected graph $G=(V,E)$ with $|V|=n$ and $|E|=m$, and parameters $0 < \varepsilon, δ<1$, along with \texttt{Degree}, \texttt{Neighbour}, \texttt{Edge} and \texttt{RandomEdge} query access to $G$, we provide a query based randomized algorithm to generate an estimate $\widehat{T}$ of the number of triangles $T$ in $G$, such that $\widehat{T} \in [(1-\varepsilon)T , (1+\varepsilon)T]$ with probability at least $1-δ$. The query complexity of our algorithm is $\widetilde{O}\left({m α\log(1/δ)}/{\varepsilon^3 T}\right)$, where $α$ is the arboricity of $G$. Our work can be seen as a continuation in 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 \texttt{RandomEdge} query. Of these works, Eden et al. [SODA 2020] considers the role of arboricity. Our work considers how \texttt{RandomEdge} query can leverage the notion of arboricity. Furthermore, continuing in the line of work of Assadi et al. [APPROX/RANDOM 2022], we also provide a lower bound of $\widetildeΩ\left({m α\log(1/δ)}/{\varepsilon^2 T}\right)$ that matches the upper bound exactly on arboricity and the parameter $δ$ and almost on $\varepsilon$.