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|
Fiala, J., & Paulusma, D. (2003). The computational complexity of the role assignment problem. In J. C. M. Baeten, J. K. Lenstra, J. Parrow, & G. J. Woeginger (Eds.), Automata, Languages and Programming : 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 – July 4, 2003 Proceedings (pp. 817-828). (Lecture notes in computer science; Vol. 2719). Springer. https://doi.org/10.1007/3-540-45061-0_64