The computational complexity of the role assignment problem

J. Fiala, Daniël Paulusma

Research output: Book/ReportReportProfessional

15 Citations (Scopus)
199 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\to 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 {\sf NP}-complete problem for any connected graph $R$ on at least three vertices. In this paper we prove the conjecture and show further corollaries for disconnected graphs and related problems.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages17
ISBN (Print)0169-2690
Publication statusPublished - 2003

Publication series

NameMemorandum Afdeling TW
PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


  • METIS-213722
  • MSC-03D15
  • EWI-3488
  • IR-65854
  • MSC-05C15

Cite this