### 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 → 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 NP-complete problem for any connected graph R on at least three vertices. In this paper we prove this conjecture, i.e. we give a complete complexity classification of the role assignment problem for connected graphs. We show further corollaries for disconnected graphs and related problems.

Original language | English |
---|---|

Title of host publication | Automata, Languages and Programming |

Subtitle of host publication | 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 – July 4, 2003 Proceedings |

Editors | J.C.M. Baeten, J.K. Lenstra, J. Parrow, G.J. Woeginger |

Publisher | Springer |

Pages | 817-828 |

ISBN (Electronic) | 978-3-540-45061-0 |

ISBN (Print) | 978-3-540-40493-4 |

DOIs | |

Publication status | Published - 2003 |

### Publication series

Name | Lecture notes in computer science |
---|---|

Volume | 2719 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Keywords

- METIS-213429

## Fingerprint Dive into the research topics of 'The computational complexity of the role assignment problem'. Together they form a unique fingerprint.

## Cite this

Fiala, J., & Paulusma, D. (2003). The computational complexity of the role assignment problem. In J. C. M. Baeten, J. K. Lenstra, J. Parrow, & G. J. Woeginger (Eds.),

*Automata, Languages and Programming : 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 – July 4, 2003 Proceedings*(pp. 817-828). (Lecture notes in computer science; Vol. 2719). Springer. https://doi.org/10.1007/3-540-45061-0_64