The twisted conjugacy problem for finitely generated free groups

Let G be a finitely generated free group and let φ∈End(G) be an endomorphism of G. In this paper we prove that the twisted conjugacy problem for φ is algorithmically solvable in the special case of φ having remnant. This case covers a significant set of endomorphisms. It is proved in Wagner (1999) [14] that almost all endomorphisms of G have remnant in a sense that can be made precise in terms of probability.For φ∈End(G) having remnant, we provide an upper bound on the length of elements z∈G that need to be checked to solve the twisted conjugate problem for φ so that the algorithm is simple to use for a computer search. Our new algorithm improves on existing algorithms which can only handle homomorphisms with remnant words of length at least 2.