2012/01/31 by Danny Dolev, Dolev, Danny, Christoph Lenzen +3 · 3 citations
Computer Science · Mathematics · #68M14 #68R10 #Advanced Graph Theory Research #C.2.4 #Complexity and Algorithms in Graphs #Distributed #F.2 #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1201.6652
openalex publication_date 2012/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G = (V,E) be an n-vertex graph and Md a d-vertex graph, for some\nconstant d. Is Md a subgraph of G? We consider this problem in a model where\nall n processes are connected to all other processes, and each message contains\nup to O(log n) bits. A simple deterministic algorithm that requires\nO(n^((d-2)/d) / log n) communication rounds is presented. For the special case\nthat Md is a triangle, we present a probabilistic algorithm that requires an\nexpected O(ceil(n^(1/3) / (t^(2/3) + 1))) rounds of communication, where t is\nthe number of triangles in the graph, and O(minn^(1/3) log^(2/3) n / (t^(2/3)\n+ 1), n^(1/3)) with high probability.\n We also present deterministic algorithms specially suited for sparse graphs.\nIn any graph of maximum degree Delta, we can test for arbitrary subgraphs of\ndiameter D in O(ceil(Delta^(D+1) / n)) rounds. For triangles, we devise an\nalgorithm featuring a round complexity of O(A2 / n + log_(2+n/A2) n), where A\ndenotes the arboricity of G.\n