Distributed Triangle Detection via Expander Decomposition
share
We present improved distributed algorithms for triangle detection and its variants in the CONGEST model. We show that Triangle Detection, Counting, and Enumeration can be solved in Õ(n^1/2) rounds. In contrast, the previous state-of-the-art bounds for Triangle Detection and Enumeration were Õ(n^2/3) and Õ(n^3/4), respectively, due to Izumi and LeGall (PODC 2017). The main technical novelty in this work is a distributed graph partitioning algorithm. We show that in Õ(n^1-δ) rounds we can partition the edge set of the network G=(V,E) into three parts E=E_m∪ E_s∪ E_r such that (a) Each connected component induced by E_m has minimum degree Ω(n^δ) and conductance Ω(1/poly(n)). As a consequence the mixing time of a random walk within the component is O(poly(n)). (b) The subgraph induced by E_s has arboricity at most n^δ. (c) |E_r| ≤ |E|/6. All of 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 due to Ghaffari, Kuhn, and Su (PODC 2017) for high conductance graphs.
READ FULL TEXT