The Computational Complexity of the Role Assignment Problem

A graph G is R-role assignable if there is a locally surjective homomorphism from G to R, i.e. a vertex mapping r : V_G → V_R, such that the neighborhood relation is preserved: r(N_G (u)) = N_R(r(u)). Kristiansen and Telle conjectured that the decision problem whether such a mapping exists is an NP-complete problem for any connected graph R on at least three vertices. In this paper we prove this conjecture, i.e. we give a complete complexity classification of the role assignment problem for connected graphs. We show further corollaries for disconnected graphs and related problems.