We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Computing role assignments of proper interval graphs in polynomial time.

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


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.

Item Type:Article
Keywords:Role assignment, Locally surjective homomorphism, Proper interval graph.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher 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
Date accepted:No date available
Date deposited:17 April 2013
Date of first online publication:July 2012
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar