Near-optimal Distributed Triangle Enumeration via Expander Decompositions

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.