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.
There has also been some recent research for the subgraph detection problem in the model. For example, @cite_2 designed an @math round algorithm for @math detection, and @cite_12 and Korhonen and Rybicki @cite_10 obtained path and tree detection algorithms requiring only a constant number of rounds. Korhonen and Rybicki @cite_10 considered also deterministic subgraph detection (for paths, cycles, trees, pseudotrees, and on @math -degenerate graphs) in the weaker broadcast model, where nodes send the same message to all neighbors in each communication round. In the model, deterministic subgraph detection algorithms were given by @cite_1 and Censor- @cite_8 .
@cite_8 @cite_1 @cite_2 @cite_10 @cite_12
2619212641 2626796510 1992996565 2107282727
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. In the standard CONGEST model for distributed network computing, it is known that "global" tasks such as minimum spanning tree, diameter, and all-pairs shortest paths, consume large bandwidth, for their running-time is @math rounds in @math -node networks with constant diameter. Surprisingly, "local" tasks such as detecting the presence of a 4-cycle as a subgraph also requires @math rounds, even using randomized algorithms, and the best known upper bound for detecting the presence of a 3-cycle is @math rounds. The objective of this paper is to better understand the landscape of such subgraph detection tasks. We show that, in contrast to , which are hard to detect in the CONGEST model, there exists a deterministic algorithm for detecting the presence of a subgraph isomorphic to @math running in a number of rounds, for every tree @math . Our algorithm provides a distributed implementation of a combinatorial technique due to Erd o for sparsening the set of partial solutions kept by the nodes at each round. Our result has important consequences to , i.e., to randomized algorithms whose aim is to distinguish between graphs satisfying a property, and graphs far from satisfying that property. In particular, we get that, for every graph pattern @math composed of an edge and a tree connected in an arbitrary manner, there exists a distributed testing algorithm for @math -freeness, performing in a constant number of rounds. Although the class of graph patterns @math formed by a tree and an edge connected arbitrarily may look artificial, all previous results of the literature concerning testing @math -freeness for classical patterns such as cycles and cliques can be viewed as direct consequences of our result, while our algorithm enables testing more complex patterns. We study two fundamental graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the well-studied Congested Clique model, and present several new bounds on the time and message complexities of randomized algorithms for these problems. No non-trivial (i.e., super-constant) time lower bounds are known for either of the aforementioned problems; in particular, an important open question is whether or not constant-round algorithms exist for these problems. We make progress toward answering this question by presenting randomized Monte Carlo algorithms for both problems that run in O(log log log n) rounds (where n is the size of the clique). Our results improve by an exponential factor on the long-standing (deterministic) time bound of O(log log n) rounds for these problems due to (SICOMP 2005). Our algorithms make use of several algorithmic tools including graph sketching, random sampling, and fast sorting. The second contribution of this paper is to present several almost-tight bounds on the message complexity of these problems. Specifically, we show that Ω(n2) messages are needed by any algorithm (including randomized Monte Carlo algorithms, and regardless of the number of rounds) that solves the GC (and hence also the MST) problem if each machine in the Congested Clique has initial knowledge only of itself (the so-called KT0 model). In contrast, if the machines have initial knowledge of their neighbors' IDs (the so-called KT1 model), we present a randomized Monte Carlo algorithm for MST that uses O(n polylog n) messages and runs in O(polylog n) rounds. To complement this, we also present a lower bound in the KT1 model that shows that Ω(n) messages are required by any algorithm that solves GC, regardless of the number of rounds used. Our results are a step toward understanding the power of randomization in the Congested Clique with respect to both time and message complexity. Given a simple graph G=(V,E) and a set of sources S ⊆ V, denote for each node ν e V by Lν(∞) the lexicographically ordered list of distance source pairs (d(s,v),s), where s ∈ S. For integers d,k ∈ N∪ ∞ , we consider the source detection, or (S,d,k)-detection task, requiring each node v to learn the first k entries of Lν(∞) (if for all of them d(s,v) ≤ d) or all entries (d(s,v),s) ∈ Lν(∞) satisfying that d(s,v) ≤ d (otherwise). Solutions to this problem provide natural generalizations of concurrent breadth-first search (BFS) tree constructions. For example, the special case of k=∞ requires each source s ∈ S to build a complete BFS tree rooted at s, whereas the special case of d=∞ and S=V requires constructing a partial BFS tree comprising at least k nodes from every node in V. In this work, we give a simple, near-optimal solution for the source detection task in the CONGEST model, where messages contain at most O(log n) bits, running in d+k rounds. We demonstrate its utility for various routing problems, exact and approximate diameter computation, and spanner construction. For those problems, we obtain algorithms in the CONGEST model that are faster and in some cases much simpler than previous solutions.