The problem of detecting network structures plays a central role in distributed computing. One of the fundamental problems studied in this area is to determine whether for a given graph @math , the input network contains a subgraph isomorphic to @math or not. We investigate this problem for @math being a clique @math in the classical distributed CONGEST model, where the communication topology is the same as the topology of the underlying network, and with limited communication bandwidth on the links. Our first and main result is a lower bound, showing that detecting @math requires @math communication rounds, for every @math , and @math rounds for every @math , where @math is the bandwidth of the communication links. This result is obtained by using a reduction to the set disjointness problem in the framework of two-party communication complexity. We complement our lower bound with a two-party communication protocol for listing all cliques in the input graph, which up to constant factors communicates the same number of bits as our lower bound for @math detection. This demonstrates that our lower bound cannot be improved using the two-party communication framework.
In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an @math round matrix multiplication algorithm, where @math is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include: -- triangle and 4-cycle counting in @math rounds, improving upon the @math triangle detection algorithm of [DISC 2012], -- a @math -approximation of all-pairs shortest paths in @math rounds, improving upon the @math -round @math -approximation algorithm of Nanongkai [STOC 2014], and -- computing the girth in @math rounds, which is the first non-trivial solution in this model. In addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles. 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 O(log n) bits. A simple deterministic algorithm that requires O(n^((d-2) d) log n) communication rounds is presented. For the special case that M_d is a triangle, we present a probabilistic algorithm that requires an expected O(ceil(n^(1 3) (t^(2 3) + 1))) rounds of communication, where t is the number of triangles in the graph, and O(min n^(1 3) log^(2 3) n (t^(2 3) + 1), n^(1 3) ) with high probability. We also present deterministic algorithms specially suited for sparse graphs. In any graph of maximum degree Delta, we can test for arbitrary subgraphs of diameter D in O(ceil(Delta^(D+1) n)) rounds. For triangles, we devise an algorithm featuring a round complexity of O(A^2 n + log_(2+n A^2) n), where A denotes the arboricity of G. We study the computation power of the congested clique, a model of distributed computation where n players communicate with each other over a complete network in order to compute some function of their inputs. The number of bits that can be sent on any edge in a round is bounded by a parameter b We consider two versions of the model: in the first, the players communicate by unicast, allowing them to send a different message on each of their links in one round; in the second, the players communicate by broadcast, sending one message to all their neighbors. It is known that the unicast version of the model is quite powerful; to date, no lower bounds for this model are known. In this paper we provide a partial explanation by showing that the unicast congested clique can simulate powerful classes of bounded-depth circuits, implying that even slightly super-constant lower bounds for the congested clique would give new lower bounds in circuit complexity. Moreover, under a widely-believed conjecture on matrix multiplication, the triangle detection problem, studied in [8], can be solved in O(ne) time for any e > 0. The broadcast version of the congested clique is the well-known multi-party shared-blackboard model of communication complexity (with number-in-hand input). This version is more amenable to lower bounds, and in this paper we show that the subgraph detection problem studied in [8] requires polynomially many rounds for several classes of subgraphs. We also give upper bounds for the subgraph detection problem, and relate the hardness of triangle detection in the broadcast congested clique to the communication complexity of set disjointness in the 3-party number-on-forehead model. We present simple deterministic algorithms for subgraph finding and enumeration in the broadcast CONGEST model of distributed computation: -- For any constant @math , detecting @math -paths and trees on @math nodes can be done in constantly many rounds, and @math -cycles in @math rounds. -- On @math -degenerate graphs, cliques and @math -cycles can be enumerated in @math rounds, and @math -cycles in @math rounds. In many cases, these bounds are tight up to logarithmic factors. Moreover, we show that the algorithms for @math -degenerate graphs can be improved to optimal complexity @math and @math , respectively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique. 