Skip to main content

Research Repository

Advanced Search

Computing role assignments of proper interval graphs in polynomial time

Heggernes, P.; van 't Hof, P.; Paulusma, D.

Computing role assignments of proper interval graphs in polynomial time Thumbnail


P. Heggernes

P. van 't Hof


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


Heggernes, P., van 't Hof, P., & Paulusma, D. (2012). Computing role assignments of proper interval graphs in polynomial time. Journal of discrete algorithms, 14, 173-188.

Journal Article Type Article
Publication Date Jul 1, 2012
Deposit Date Mar 11, 2013
Publicly Available Date Apr 17, 2013
Journal Journal of Discrete Algorithms
Print ISSN 1570-8667
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 14
Pages 173-188
Keywords Role assignment, Locally surjective homomorphism, Proper interval graph.


Accepted Journal Article (471 Kb)

Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in Journal of discrete algorithms. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Journal of discrete algorithms, 14, 2012, 10.1016/j.jda.2011.12.004

You might also like

Downloadable Citations