The computational complexity of the role assignment problem

J. Fiala, Daniël Paulusma

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

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.
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
PublisherSpringer
Pages817-828
ISBN (Electronic)978-3-540-45061-0
ISBN (Print)978-3-540-40493-4
DOIs
Publication statusPublished - 2003

Publication series

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

Keywords

  • METIS-213429

Fingerprint Dive into the research topics of 'The computational complexity of the role assignment problem'. Together they form a unique fingerprint.

  • Cite this

    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