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.
|Title of host publication||Automata, Languages and Programming |
|Subtitle of host publication||30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 – July 4, 2003 Proceedings|
|Editors||J.C.M. Baeten, J.K. Lenstra, J. Parrow, G.J. Woeginger|
|Publication status||Published - 2003|
|Name||Lecture notes in computer science|