Computing role assignments of proper interval graphs in polynomial time

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationCombinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers
EditorsCostas S. Iliopoulos, William F. Smyth
PublisherSpringer Singapore
Number of pages14
ISBN (Electronic)978-3-642-19222-7
ISBN (Print)978-3-642-19221-0
Publication statusPublished - 2010
Externally publishedYes
Event21st International Workshop on Combinatorial Algorithms, IWOCA 2010 - London, United Kingdom
Duration: 26 Jul 201028 Jul 2010
Conference number: 21

Publication series

NameLecture Notes in Computer Science


Conference21st International Workshop on Combinatorial Algorithms, IWOCA 2010
Abbreviated titleIWOCA 2010
CountryUnited Kingdom


Dive into the research topics of 'Computing role assignments of proper interval graphs in polynomial time'. Together they form a unique fingerprint.

Cite this