# The computational complexity of the role assignment problem

J. Fiala, Daniël Paulusma

Research output: Book/ReportReportProfessional

11 Citations (Scopus)

### 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 language Undefined Enschede University of Twente, Department of Applied Mathematics 17 0169-2690 Published - 2003

### Publication series

Name Memorandum Afdeling TW Department of Applied Mathematics, University of Twente 1668 0169-2690

• 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.