Yi-Jun Chang
Distributed Triangle Detection via Graph Partitioning

Abstract: We present improved distributed algorithms for triangle detection and
its variants in the CONGEST model. We show that the triangle detection
and listing problems can be solved in $O(n^{1-1/\omega+o(1)}) <
O(n^{0.58})$ and $O(n^{2/3+o(1)})$ rounds, respectively. In
comparison, the previous state-of-the-art bounds for these two
problems was $\tilde{O}(n^{2/3})$ and $\tilde{O}(n^{3/4})$,
respectively, due to Izumi and Le Gall (PODC 2017).

The main technical novelty in this work is a distributed graph
partitioning algorithm. We show that in $\tilde{O}(n^{1-\delta})$
rounds we can partition the edge set of the network $G=(V,E)$ into
three parts $E=E_m\cup E_s\cup E_r$ such that

(a) Each connected component induced by $E_m$ has minimum degree
$\Omega(n^\delta)$ and conductance $\Omega(1/\polylog(n))$. As a
consequence the mixing time of a random walk within the component is
$\polylog(n)$.

(b) The subgraph induced by $E_s$ has arboricity $O(n^{\delta})$. 

(c)  $|E_r|  <  |E|/2$.

All our algorithms are based on the following generic framework, which
we believe is of interest beyond this work. Roughly, we deal with the
set $E_s$ by an algorithm that is efficient for low-arboricity graphs,
and deal with the set $E_r$ using recursive calls.  For each connected
component induced by $E_m$, we are able to simulate Congested Clique
algorithms with small overhead by applying a routing algorithm for
high conductance graphs (Ghaffari, Kuhn, and Su, PODC 2017).

This is a joint work with Seth Pettie and Hengjie Zhang.