Distributed triangle detection via expander decomposition

DOI10.1137/1.9781611975482.51MaRDI QIDQ5236234zbMATH OpenOpenAlexFDO

Authors Yi-Jun Chang, Seth Pettie, Hengjie Zhang

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.06624

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Distributed algorithms (68W15)

Abstract: 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 $ildeO(n^{1/2})$ rounds. In contrast, the previous state-of-the-art bounds for Triangle Detection and Enumeration were $ildeO(n^{2/3})$ and $ildeO(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 $ildeO(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^{d}elta)$ and conductance $Omega(1/extpolylog(n))$. As a consequence the mixing time of a random walk within the component is $O(extpolylog(n))$. (b) The subgraph induced by $E_s$ has arboricity at most $n^{delta}$. (c) $|E_r|leq|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.

Recommendations

• Near-optimal Distributed Triangle Enumeration via Expander Decompositions
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Triangle Finding and Listing in CONGEST Networks
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• On the power of the congested clique model

Cited in

(19)

• Listing 4-cycles
• Fooling views: a new lower bound technique for distributed computations under congestion
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Near-optimal Distributed Triangle Enumeration via Expander Decompositions
• Distributed detection of cliques in dynamic networks
• Near-optimal scheduling in the congested clique
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Deterministic subgraph detection in broadcast CONGEST
• Distributed subgraph finding: progress and challenges (invited talk)
• Fast distributed algorithms for girth, cycles and small subgraphs
• Detecting cliques in CONGEST networks
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• Detecting cliques in CONGEST networks
• A note on improved results for one round distributed clique listing
• Fast approximate shortest paths in the congested clique
• The communication complexity of set intersection and multiple equality testing
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• Deterministic near-optimal distributed listing of cliques
• Finding a small vertex cut on distributed networks

This page was built for publication: Distributed triangle detection via expander decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236234)