The computational complexity of the role assignment problem

J. Fiala, Daniël Paulusma

Research output: Book/ReportReportProfessional

11 Citations (Scopus)
139 Downloads (Pure)

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\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
No.1668
ISSN (Print)0169-2690

Keywords

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

Cite this

Fiala, J., & Paulusma, D. (2003). The computational complexity of the role assignment problem. (Memorandum Afdeling TW; No. 1668). Enschede: University of Twente, Department of Applied Mathematics.