2024/05/01 by Quanquan C. Liu, Liu, Quanquan C., C. Seshadhri +1 · 2 citations
Computer Science · Engineering · #3D Shape Modeling and Analysis #Advanced Numerical Analysis Techniques #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Image Processing and 3D Reconstruction #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2405.00262
openalex publication_date 2024/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this short note, we give a novel algorithm for O(1) round triangle counting in bounded arboricity graphs. Counting triangles in O(1) rounds (exactly) is listed as one of the interesting remaining open problems in the recent survey of Im et al. [IKLMV23]. The previous paper of Biswas et al. [BELMR20], which achieved the best bounds under this setting, used O(log log n) rounds in sublinear space per machine and O(mα) total space where α is the arboricity of the graph and n and m are the number of vertices and edges in the graph, respectively. Our new algorithm is very simple, achieves the optimal O(1) rounds without increasing the space per machine and the total space, and has the potential of being easily implementable in practice.