@inproceedings{e18d3ae2b5aa464983b7e4f464fc9ed3,

title = "The computational complexity of the role assignment problem",

abstract = "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.",

keywords = "METIS-213429",

author = "J. Fiala and Dani{\"e}l Paulusma",

year = "2003",

doi = "10.1007/3-540-45061-0_64",

language = "English",

isbn = "978-3-540-40493-4",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "817--828",

editor = "J.C.M. Baeten and J.K. Lenstra and J. Parrow and G.J. Woeginger",

booktitle = "Automata, Languages and Programming",

address = "Netherlands",

}