On the Complexity of Epimorphism Testing with Virtually Abelian Targets

Abstract

Friedl and Löh (2021, Confl. Math.) prove that testing whether or not there is an epimorphism from a finitely presented group to the direct product of an abelian and a finite group, or to a virtually cyclic group, is decidable. Here we prove that these problems are NP-complete. In addition we show that testing epimorphism is NP-complete when the target is a restricted type of semi-direct product of a finitely generated free abelian group and a finite group, thus extending the class of virtually abelian target groups for which decidability of epimorphism is known. We also consider epimorphism from a finitely presented group to a fixed finite group. We show the epimorphism problem is NP-complete when the target is a dihedral group of order that is not a power of 2, complementing the work on Kuperberg and Samperton (2018, Geom. Topol.) who showed the same result when the target is non-Abelian finite simple.