  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.
