## Computing role assignments of proper interval graphs in polynomial time

*Pinar Heggernes, Pim van 't Hof and Daniël Paulusma*

*Journal of Discrete Algorithms*, vol. 14, pp. 173-188, 2012.

[__DOI__][__Preprint__]

A preliminary version of this paper appeared in the proceedings of IWOCA 2010, the 21st International Workshop on Combinatorial Algorithms (held on July 26-28, 2010, London, United Kingdom), *Lecture Notes in Computer Science*, vol. 6460, pp. 167-180, 2011.

[__DOI__]

### Abstract:

An *R*-role assignment of a graph *G* is a locally surjective
homomorphism from *G* to graph *R*.
For a fixed graph *R*, the *R*-Role Assignment problem is to decide, for an input graph *G*,
whether *G* has an *R*-role assignment.
When both graphs *G* and *R* are given as input, the problem is called Role Assignment. In this paper, we study the latter problem. It is known that
*R*-Role Assignment is NP-complete already when *R* is a path on three vertices. In order to obtain polynomial time algorithms for Role Assignment, it is therefore necessary to put restrictions on *G*. So far, the only known non-trivial case for which this problem is solvable in polynomial time is when *G* is a tree.
We present an algorithm that solves Role Assignment in polynomial time when *G* is a proper interval graph.
Thus we identify the first graph class other than trees on which the problem is tractable.
As a complementary result, we show that Role Assignment is Graph Isomorphism-hard on chordal graphs, a superclass of proper interval graphs and trees.