### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 17 |

ISBN (Print) | 0169-2690 |

Publication status | Published - 2003 |

### Publication series

Name | Memorandum Afdeling TW |
---|---|

Publisher | Department 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

*The computational complexity of the role assignment problem*. (Memorandum Afdeling TW; No. 1668). Enschede: University of Twente, Department of Applied Mathematics.

}

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

Research output: Book/Report › Report › Professional

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 -