Computing Role Assignments of Proper Interval Graphs in Polynomial Time

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

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.

Citation

Heggernes, P., Hof, V. P., & Paulusma, D. (2011, December). Computing Role Assignments of Proper Interval Graphs in Polynomial Time. Presented at 21st International Workshop on Combinatorial Algorithms, IWOCA 2010, London

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 21st International Workshop on Combinatorial Algorithms, IWOCA 2010
• Publication Date: Jan 1, 2011
• Deposit Date: Dec 21, 2014
• Publicly Available Date: Apr 13, 2016
• Print ISSN: 0302-9743
• Pages: 167-180
• Series Title: Lecture notes in computer science
• Series Number: 6460
• Series ISSN: 0302-9743,1611-3349
• Book Title: Combinatorial algorithms : 21st International Workshop, IWOCA 2010, London, July 26-28, 2010, revised selected papers
• ISBN: 9783642192210
• DOI: https://doi.org/10.1007/978-3-642-19222-7_18
• Public URL: https://durham-repository.worktribe.com/output/1153773