# 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.
Fiala, J. ; Paulusma, Daniël. / The computational complexity of the role assignment problem. Enschede : University of Twente, Department of Applied Mathematics, 2003. 17 p. (Memorandum Afdeling TW; 1668).
@book{612d65a479f6423faeb9146ef11f982e,
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\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.",
keywords = "METIS-213722, MSC-03D15, EWI-3488, IR-65854, MSC-05C15",
author = "J. Fiala and Dani{\"e}l Paulusma",
note = "Imported from MEMORANDA",
year = "2003",
language = "Undefined",
isbn = "0169-2690",
series = "Memorandum Afdeling TW",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1668",

}

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

The computational complexity of the role assignment problem. / Fiala, J.; Paulusma, Daniël.

Enschede : University of Twente, Department of Applied Mathematics, 2003. 17 p. (Memorandum Afdeling TW; No. 1668).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - The computational complexity of the role assignment problem

AU - Fiala, J.

AU - Paulusma, Daniël

N1 - Imported from MEMORANDA

PY - 2003

Y1 - 2003

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

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

KW - METIS-213722

KW - MSC-03D15

KW - EWI-3488

KW - IR-65854

KW - MSC-05C15

M3 - Report

SN - 0169-2690

T3 - Memorandum Afdeling TW

BT - The computational complexity of the role assignment problem

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

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