Improved Massively Parallel Triangle Counting in $O(1)$ Rounds
<|reference_start|>Improved Massively Parallel Triangle Counting in $O(1)$ Rounds: 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\alpha)$ total space where $\alpha$ 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.<|reference_end|>
@article{liu2024improved,
    title={Improved Massively Parallel Triangle Counting in $O(1)$ Rounds},
    author={Quanquan C. Liu and C. Seshadhri},
    journal={arXiv preprint arXiv:2405.00262},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.00262},
    primaryClass={cs.DS cs.DC}
}