"Tri, Tri Again": Finding Triangles and Small Subgraphs in a Distributed Setting - (Extended Abstract)
Abstract. Let G = (V,E) be an n-vertex graph and Md a d-vertex graph, for some constant d. Is Md a subgraph of G? We consider this problem in a model where all n processes are connected to all other pro-cesses, and each message contains up to O(logn) bits. A simple determin-istic algorithm that requires O(n(d−2)/d / logn) communication rounds is presented. For the special case that Md is a triangle, we present a prob-abilistic algorithm that requires an expected O(n1/3/(t2/3 + 1)) rounds of communication, where t is the number of triangles in the graph, and O(min{n1/3 log2/3 n/(t2/3 + 1), n1/3}) 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 O(∆D+1/n) rounds. For triangles, we devise an algorithm featuring a round complexity of O((A2 log2+n/A2 n)/n), where A denotes the arboricity of G. 1