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 $\Omega(\mbox{ poly}(n))$ rounds in $n$-node networks with constant diameter. Surprisingly, "local" tasks such as detecting the presence of a 4-cycle as a subgraph also requires $\widetilde{ \Omega}(\sqrt{ n})$ rounds, even using randomized algorithms, and the best known upper bound for detecting the presence of a 3-cycle is $\widetilde{ O}(n^{ \frac{ 2}{ 3}})$ rounds. The objective of this paper is to better understand the landscape of such subgraph detection tasks. We show that, in contrast to \emph{ cycles}, which are hard to detect in the CONGEST model, there exists a deterministic algorithm for detecting the presence of a subgraph isomorphic to $T$ running in a \emph{ constant} number of rounds, for every tree $T$. Our algorithm provides a distributed implementation of a combinatorial technique due to Erd\H{ o}s et al. for sparsening the set of partial solutions kept by the nodes at each round. Our result has important consequences to \emph{ distributed property-testing}, 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 $H$ composed of an edge and a tree connected in an arbitrary manner, there exists a distributed testing algorithm for $H$-freeness, performing in a constant number of rounds. Although the class of graph patterns $H$ formed by a tree and an edge connected arbitrarily may look artificial, all previous results of the literature concerning testing $H$-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.
Categories: cs.DC