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

CREATORArijit Bishnu, Debarshi Chanda, Gopinath Mishra
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text