@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 = "Germany",
}