  In this paper we consider the fundamental problem of finding subgraphs in
highly dynamic distributed networks - networks which allow an arbitrary number
of links to be inserted / deleted per round. We show that the problems of
$k$-clique membership listing (for any $k\geq 3$), 4-cycle listing and 5-cycle
listing can be deterministically solved in $O(1)$-amortized round complexity,
even with limited logarithmic-sized messages.
  To achieve $k$-clique membership listing we introduce a very useful
combinatorial structure which we name the robust $2$-hop neighborhood. This is
a subset of the 2-hop neighborhood of a node, and we prove that it can be
maintained in highly dynamic networks in $O(1)$-amortized rounds. We also show
that maintaining the actual 2-hop neighborhood of a node requires near linear
amortized time, showing the necessity of our definition. For $4$-cycle and
$5$-cycle listing, we need edges within hop distance 3, for which we similarly
define the robust $3$-hop neighborhood and prove it can be maintained in highly
dynamic networks in $O(1)$-amortized rounds.
  We complement the above with several impossibility results. We show that
membership listing of any other graph on $k\geq 3$ nodes except $k$-clique
requires an almost linear number of amortized communication rounds. We also
show that $k$-cycle listing for $k\geq 6$ requires $\Omega(\sqrt{n} / \log n)$
amortized rounds. This, combined with our upper bounds, paints a detailed
picture of the complexity landscape for ultra fast graph finding algorithms in
this highly dynamic environment.
