Near-optimal Distributed Triangle Enumeration via Expander Decompositions
- 13 May 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (3), 1-36
- https://doi.org/10.1145/3446330
Abstract
We present improved distributed algorithms for variants of the triangle finding problem in the \(\) model. We show that triangle detection, counting, and enumeration can be solved in \(\) rounds using expander decompositions. This matches the triangle enumeration lower bound of \(\) by Izumi and Le Gall [PODC’17] and Pandurangan, Robinson, and Scquizzato [SPAA’18], which holds even in the \(\) model. The previous upper bounds for triangle detection and enumeration in \(\) were \(\) and \(\), respectively, due to Izumi and Le Gall [PODC’17]. An \(\)-expander decomposition of a graph \(\) is a clustering of the vertices \(\) such that (i) each cluster \(\) induces a subgraph with conductance at least \(\) and (ii) the number of inter-cluster edges is at most \(\). We show that an \(\)-expander decomposition with \(\) can be constructed in \(\) rounds for any \(\) and positive integer \(\). For example, a \(\)-expander decomposition only requires \(\) rounds to compute, which is optimal up to subpolynomial factors, and a \(\)-expander decomposition can be computed in \(\) rounds, for any arbitrarily small constant \(\). Our triangle finding algorithms are based on the following generic framework using expander decompositions, which is of independent interest. We first construct an expander decomposition. For each cluster, we simulate \(\) algorithms with small overhead by applying the expander routing algorithm due to Ghaffari, Kuhn, and Su [PODC’17] Finally, we deal with inter-cluster edges using recursive calls.
Keywords
Funding Information
- NSF (CCF-1514383, CCF-1637546, and CCF-1815316)
This publication has 51 references indexed in Scilit:
- Spectral Sparsification of GraphsSIAM Journal on Computing, 2011
- Expander flows, geometric embeddings and graph partitioningJournal of the ACM, 2009
- On clusteringsJournal of the ACM, 2004
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree ConstructionSIAM Journal on Computing, 2000
- Fast Distributed Construction of Smallk-Dominating Sets and ApplicationsJournal of Algorithms, 1998
- Low‐diameter graph decomposition is in NCRandom Structures & Algorithms, 1994
- Low diameter graph decompositionsCombinatorica, 1993
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random StartSIAM Journal on Matrix Analysis and Applications, 1992
- Approximating the PermanentSIAM Journal on Computing, 1989
- Approximate counting, uniform generation and rapidly mixing Markov chainsInformation and Computation, 1989