  In various occasions the conjugacy problem in finitely generated amalgamated
products and HNN extensions can be decided efficiently for elements which
cannot be conjugated into the base groups. This observation asks for a bound on
how many such elements there are. Such bounds can be derived using the theory
of amenable graphs:
  In this work we examine Schreier graphs of amalgamated products and HNN
extensions. For an amalgamated product $G = H *_A K $ with $[H:A] \geq [K:A]
\geq 2$, the Schreier graph with respect to $H$ or $K$ turns out to be
non-amenable if and only if $[H:A] \geq 3$. Moreover, for an HNN extension of
the form $G = <H,b | bab^{-1}=\phi(a), a \in A >$, we show that the Schreier
graph of $G$ with respect to the subgroup $H$ is non-amenable if and only if $A
\neq H \neq \phi(A)$.
  As application of these characterizations we show that under certain
conditions the conjugacy problem in fundamental groups of finite graphs of
groups with free abelian vertex groups can be solved in polynomial time on a
strongly generic set. Furthermore, the conjugacy problem in groups with more
than one end can be solved with a strongly generic algorithm which has
essentially the same time complexity as the word problem. These are rather
striking results as the word problem might be easy, but the conjugacy problem
might be even undecidable. Finally, our results yield another proof that the
set where the conjugacy problem of the Baumslag group is decidable in
polynomial time is also strongly generic.
