  In this paper we study detection and reconstruction of planted structures in
Erd\H{o}s-R\'enyi random graphs. Motivated by a problem of communication
security, we focus on planted structures that consist in a tree graph. For
planted line graphs, we establish the following phase diagram. In a low density
region where the average degree $\lambda$ of the initial graph is below some
critical value $\lambda_c=1$, detection and reconstruction go from impossible
to easy as the line length $K$ crosses some critical value $f(\lambda)\ln(n)$,
where $n$ is the number of nodes in the graph. In the high density region
$\lambda>\lambda_c$, detection goes from impossible to easy as $K$ goes from
$o(\sqrt{n})$ to $\omega(\sqrt{n})$, and reconstruction remains impossible so
long as $K=o(n)$. For $D$-ary trees of varying depth $h$ and $2\le D\le O(1)$,
we identify a low-density region $\lambda<\lambda_D$, such that the following
holds. There is a threshold $h*=g(D)\ln(\ln(n))$ with the following properties.
Detection goes from feasible to impossible as $h$ crosses $h*$. We also show
that only partial reconstruction is feasible at best for $h\ge h*$. We
conjecture a similar picture to hold for $D$-ary trees as for lines in the
high-density region $\lambda>\lambda_D$, but confirm only the following part of
this picture: Detection is easy for $D$-ary trees of size $\omega(\sqrt{n})$,
while at best only partial reconstruction is feasible for $D$-ary trees of any
size $o(n)$. These results are in contrast with the corresponding picture for
detection and reconstruction of {\em low rank} planted structures, such as
dense subgraphs and block communities: We observe a discrepancy between
detection and reconstruction, the latter being impossible for a wide range of
parameters where detection is easy. This property does not hold for previously
studied low rank planted structures.
