Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
Arijit Bishnu, Debarshi Chanda, Gopinath Mishra · 2025
Read Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries by Arijit Bishnu, Debarshi Chanda, Gopinath Mishra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-15379.txt.
Introduction
Arijit Bishnu, Debarshi Chanda, and Gopinath Mishra wrote this 2025 mathematics paper on counting triangles in a huge graph by asking only a few questions. The head title is Arboricity Matters in Triangle Counting with Random Edges. Triangles, sets of three mutually linked nodes, are a basic sign of clustering in networks.
Their randomized algorithm estimates the triangle count within a chosen error, with high chance of success. It may ask about degrees, neighbors, pairs, and random edges of the graph. The number of questions scales with a graph trait called arboricity. That trait measures how sparse the graph is in a strong sense. The authors also prove a matching lower bound, tight on most settings. Together, the results show that random edge access plus arboricity set the true cost of the task.
Catalog record
| CREATOR | Arijit Bishnu, Debarshi Chanda, Gopinath Mishra |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-15379
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries Arijit Bishnu, Debarshi Chanda, Gopinath Mishra Abstract Given a simple, unweighted, undirected graph G = ( V , E ) G=(V,E) with | V | = n |V|=n and | E | = m |E|=m , and parameters 0 < ε , δ < 1 0<\varepsilon,\delta<1 , along with Degree , Neighbour , Edge and RandomEdge query access to G G , we provide a query based randomized algorithm to generate an estimate T ^ \widehat{T} of the number of triangles T T in G G , such that T ^ ∈ [ ( 1 − ε ) T , ( 1 + ε ) T ] \widehat{T}\in[(1-\varepsilon)T,(1+\varepsilon)T] with probability at least 1 − δ 1-\delta . The query complexity of our algorithm is O ~ ( m α log ( 1 / δ ) / ε 3 T ) \widetilde{O}\left({m\alpha\log(1/\delta)}/{\varepsilon^{3}T}\right) , where α \alpha is the arboricity of G 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 RandomEdge query. Of these works, Eden et al. [SODA 2020] considers the role of arboricity. Our work considers how 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 Ω ~ ( m α log ( 1 / δ ) / ε 2 T ) \widetilde{\Omega}\left({m\alpha\log(1/\delta)}/{\varepsilon^{2}T}\right) that matches the upper bound exactly on arboricity and the parameter δ \delta and almost on ε \varepsilon . 1 Introduction Counting the number of triangles present in graphs is a classical problem dating back to Chiba and Nishizeki, 1985 ; Alon et al., 2008 ; Schank and Wagner, 2005 ; Alon, 2013 ; Bar-Yossef et al., 2002 . Researchers in the sub-linear space (streaming) community has been looking at this problem for the last two decades; see Bar-Yossef et al., 2002 ; Bera and Chakrabarti, 2017 ; Jayaram and Kallaugher, 2021 ; Ahn et al., 2012 ; Bulteau et al., 2016 ; Alon et al., 1997 ; Jha et al., 2015 ; Buriol et al., 2006 ; Cormode and Jowhari, 2017 ; Shin et al., 2020 ; Kane et al., 2012 for a sample of such works. The problem has also been studied by the researchers in the sub-linear time (property testing) community in the last decade Eden et al., 2017 ; McGregor et al., 2016 ; Kallaugher and Price, 2017 ; Bera and Chakrabarti, 2017 ; Bera and Seshadhri, 2020 ; Eden et al., 2020 ; Jayaram and Kallaugher, 2021 . Here, graphs can be accessed only through certain queries. On the other hand, starting with the work of Chiba and Nishizeki, 1985 , the graph parameter called arboricity has also found its use in triangle counting Eden et al., 2020 . This work shows the use of arboricity in triangle counting where the graph can be accessed through a random edge query along with other standard queries like degree, neighbor and edge existence. Counting triangle has been a well motivated problem with applications across various domains like optimizing query size in database join problems ( Bar-Yossef et al., 2002 ; Atserias et al., 2013 ; Assadi et al., 2019 ) , computing clustering coefficients, transitivity ratio ( Aggarwal and Subbian, 2014 ; Luce and Perry, 1949 ; Watts and Strogatz, 1998 ; Leskovec et al., 2008 ) , studying structures in web graphs ( Eckmann and Moses, 2001 ; Danisch et al., 2018 ) etc. For a more thorough overview, see the surveys ( Al Hasan and Dave, 2018 ; Tsourakakis et al., 2011 ) . The parametrization based on arboricity is also of practical interest due to occurrence of low-arboricity graphs in various real world scenarios ( Dory et al., 2022 ; Konrad et al., 2024 ; Onak et al., 2020 ; Goel and Gustedt, 2006 ; Bera et al., 2020 ; Danisch et al., 2018 ; Shin et al., 2018 ) . Formally, we are given a simple, unweighted, undirected graph G=\left({V,E}\right) with \left|{V}\right|=n , and \left|{E}\right|=m . The set of neighbours of the vertex v is denoted by {\sf N}{\left({v}\right)} = \left\{{u|\left({u,v}\right)\in E}\right\} and the degree of the vertex v is denoted by \mbox{deg}_{v}=\left|{{\sf N}{\left({v}\right)}}\right| . We are given the following queries to access the graph: • \texttt{Degree}{(v)} : Given a vertex v , return \mbox{deg}_{v} . • \texttt{Neighbour}(v,i) : Given a v\in V and i\in\mbox{deg}_{v} , returns the i -th vertex u\in{\sf N}(v) . • \texttt{Edge}(u,v) : Given two vertices u,v\in V , returns 1 if (u,v)\in E , and 0 otherwise. • RandomEdge : Returns an edge e\in E uniformly at random. We will call the Degree , Neighbour and Edge queries taken together to be local queries . Given parameters 0<\varepsilon,\delta<1 , our task is to obtain an estimate \widehat{T} of the number of triangles T in the graph G , such that \widehat{T}\in\left[{\left({1-\varepsilon}\right)T,\left({1+\varepsilon}\right)T}\right] with probability 1-\delta . From now on, we refer \widehat{T} to be an \left({\varepsilon,\delta}\right) estimate of T . One of the graph parameters that has been relevant to quantify the complexity of triangle listing algorithms within the context of RAM model ( Chiba and Nishizeki, 1985 ) , streaming model ( Bera and Seshadhri, 2020 ) , distributed model ( Jain and Seshadhri, 2017 ; Suri and Vassilvitskii, 2011 ; Finocchi et al., 2015 ) and query model ( Eden and Rosenbaum, 2018 ) is the arboricity of the graph G , denoted \alpha . The arboricity of a graph can be seen as a measure of the density of the graph. Definition 1 (Arboricity (\alpha) ) . The arboricity of a graph G=(V,E) , denoted by \alpha , is the minimum number of spanning forests that E can be partitioned into. Recent works have established various ways to construct lower bounds incorporating the impact of \varepsilon and \delta both in graph property testing ( Assadi and Nguyen, 2022 ) and other problems ( Tětek, 2022 ) . Our lower bounds will also involve \varepsilon and \delta . To illustrate the dependence of the polylog terms, \varepsilon and \delta on the query complexity of our algorithm, we will use two notations at times in place of O\left({{\bullet}}\right) – \widetilde{O}\left({{\bullet}}\right) hides polylog factors only but shows dependence on \varepsilon and \delta , whereas \widetilde{O}_{\varepsilon,\delta}\left({{\bullet}}\right) hides both polylog and \varepsilon , \delta terms. Similarly, we will have \widetilde{\Omega}\left({{\bullet}}\right) and \widetilde{\Omega}_{\varepsilon,\delta}\left({{\bullet}}\right) . 1.1 Our Results In this section we present our results and contextualize it vis-a-vis the works of Assadi et al., 2019 ; Eden et al., 2017 ; Eden et al., 2020 ; Assadi and Nguyen, 2022 . Upper Bound. We show that using random edge queries in addition to local queries, we can obtain an \left({\varepsilon,\delta}\right) estimate of T where the query complexity is parameterized by arboricity apart from the usual parameters of edge, vertex, the number of triangles, \varepsilon and \delta . The work