“Tri, Tri Again”:
Finding Triangles and Small Subgraphs in a Distributed Setting

Summary

Let G = (V,E) be an n-vertex graph and M d a d-vertex graph, for some constant d. Is M d a subgraph of G? We consider this problem in a model where all n processes are connected to all other processes, and each message contains up to bits. A simple deterministic algorithm that requires communication rounds is presented. For the special case that M d is a triangle, we present a probabilistic algorithm that requires an expected rounds of communication, where t is the number of triangles in the graph, and with high probability. We also present deterministic algorithms that are specially suited for sparse graphs. In graphs of maximum degree Δ, we can test for arbitrary subgraphs of diameter D in rounds. For triangles, we devise an algorithm featuring a round complexity of , where A denotes the arboricity of G.