The computational complexity of the role assignment problem

J. Fiala, Daniël Paulusma

Research output: Book/ReportReportProfessional

11 Citations (Scopus)
126 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.
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).