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

Given a simple, unweighted, undirected graph $G=(V,E)$ with $\mathrm{\mid }V\mathrm{\mid }=n$ and $\mathrm{\mid }E\mathrm{\mid }=m$, and parameters $0<\epsilon ,\delta <1$, along with $\mathtt{\text{Degree}}$, $\mathtt{\text{Neighbour}}$, $\mathtt{\text{Edge}}$ and $\mathtt{\text{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-\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\mathrm{/}\delta )\mathrm{/}{\epsilon }^{3}T\right)$, where $\alpha$ 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 $\mathtt{\text{RandomEdge}}$ query. Of these works, Eden et al. [SODA 2020] considers the role of arboricity. Our work considers how $\mathtt{\text{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 $\tilde{\mathrm{\Omega }}\left(m\alpha \log (1\mathrm{/}\delta )\mathrm{/}{\epsilon }^{2}T\right)$ that matches the upper bound exactly on arboricity and the parameter $\delta$ and almost on $\epsilon$.