  We establish a connection between the generalized conjugacy problem for a
$G$-by-$\mathbb{Z}$ group, $GCP(G \rtimes \mathbb{Z})$, and two algorithmic
problems for $G$: the generalized Brinkmann's conjugacy problem, $GBrCP(G)$,
and the generalized twisted conjugacy problem, $GTCP(G)$. We explore this
connection for generalizations of different kinds: relative to finitely
generated subgroups, to theirs cosets, or to recognizable, rational,
context-free or algebraic subsets of the group. Using this result, we are able
to prove that $GBrCP(G)$ is decidable (with respect to cosets) when $G$ is a
virtually polycyclic group, which implies in particular that the generalized
Brinkmann's equality problem, $GBrP(G)$, is decidable if $G$ is a finitely
generated abelian group. Finally, we prove that if $G$ is a finitely generated
virtually free group, then the simple versions of Brinkmann's equality problem
and of the twisted conjugacy problem, $BrP(G)$ and $TCP(G)$, are decidable.
