Skip to main content

Research Repository

Advanced Search

Computing Role Assignments of Proper Interval Graphs in Polynomial Time

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

Computing Role Assignments of Proper Interval Graphs in Polynomial Time Thumbnail


Authors

P. Heggernes

van't P. Hof



Contributors

Costas S. Iliopoulos
Editor

William F. Smyth
Editor

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). Computing Role Assignments of Proper Interval Graphs in Polynomial Time. In C. S. Iliopoulos, & W. F. Smyth (Eds.), Combinatorial algorithms : 21st International Workshop, IWOCA 2010, London, July 26-28, 2010, revised selected papers (167-180). https://doi.org/10.1007/978-3-642-19222-7_18

Conference Name 21st International Workshop on Combinatorial Algorithms, IWOCA 2010
Conference Location London
Publication Date Jan 1, 2011
Deposit Date Dec 21, 2014
Publicly Available Date Mar 29, 2024
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

Files





You might also like



Downloadable Citations