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.