2018/07/17 by Yi‐Jun Chang, Seth Pettie, Chang, Yi-Jun +3 · 2 citations
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Graph Theory and Algorithms #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1807.06624
openalex publication_date 2018/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 O(n1/2) rounds. In contrast, the previous state-of-the-art bounds for Triangle Detection and Enumeration were O(n2/3) and O(n3/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 O(n1-δ) rounds we can partition the edge set of the network G=(V,E) into three parts E=Em∪ Es∪ Er such that (a) Each connected component induced by Em has minimum degree Ω(nδ) and conductance Ω(1/poly log(n)). As a consequence the mixing time of a random walk within the component is O(poly log(n)). (b) The subgraph induced by Es has arboricity at most nδ. (c) |Er| ≤ |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 Es by an algorithm that is efficient for low-arboricity graphs, and deal with the set Er using recursive calls. For each connected component induced by Em, 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.