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 Hof, van 't P. and Paulusma, D. (2011) 'Computing role assignments of proper interval graphs in polynomial time.', in Combinatorial algorithms : 21st International Workshop, IWOCA 2010, London, July 26-28, 2010, revised selected papers. Berlin; Heidelberg: Springer, pp. 167-180. Lecture notes in computer science. (6460).


A homomorphism from a graph G to a graph R is locally surjective if its restriction to the neighborhood of each vertex of G is surjective. Such a homomorphism is also called an R-role assignment of G. Role assignments have applications in distributed computing, social network theory, and topological graph theory. The Role Assignment problem has as input a pair of graphs (G,R) and asks whether G has an R-role assignment. This problem is NP-complete already on input pairs (G,R) where R is a path on three vertices. So far, the only known non-trivial tractable case consists of input pairs (G,R) where G is a tree. We present a polynomial time algorithm that solves Role Assignment on all input pairs (G,R) where 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 the problem is Graph Isomorphism-hard on chordal graphs, a superclass of proper interval graphs and trees.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:No date available
Date deposited:13 April 2016
Date of first online publication:2011
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar