The computational complexity of the role assignment problem

J. Fiala, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 – July 4, 2003 Proceedings
EditorsJ.C.M. Baeten, J.K. Lenstra, J. Parrow, G.J. Woeginger
ISBN (Electronic)978-3-540-45061-0
ISBN (Print)978-3-540-40493-4
Publication statusPublished - 2003

Publication series

NameLecture notes in computer science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


  • METIS-213429

Cite this