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)

Abstract

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
Pages167-180
Number of pages14
ISBN (Electronic)978-3-642-19222-7
ISBN (Print)978-3-642-19221-0
DOIs
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
PublisherSpringer
Volume6460

Conference

Conference21st International Workshop on Combinatorial Algorithms, IWOCA 2010
Abbreviated titleIWOCA 2010
CountryUnited Kingdom
CityLondon
Period26/07/1028/07/10

Fingerprint

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

Cite this