Computing role assignments of proper interval graphs in polynomial time

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

Abstract

An R-role assignment of a graph G is a locally surjective homomorphism from G to graph R. For a fixed graph R, the R-Role Assignment problem is to decide, for an input graph G, whether G has an R-role assignment. When both graphs G and R are given as input, the problem is called Role Assignment. In this paper, we study the latter problem. It is known that R-Role Assignment is NPNP-complete already when R is a path on three vertices. In order to obtain polynomial time algorithms for Role Assignment, it is therefore necessary to put restrictions on G. So far, the only known non-trivial case for which this problem is solvable in polynomial time is when G is a tree. We present an algorithm that solves Role Assignment in polynomial time when 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 Role Assignment is Graph Isomorphism-hard on chordal graphs, a superclass of proper interval graphs and trees.

Citation

Heggernes, P., van 't Hof, P., & Paulusma, D. (2012). Computing role assignments of proper interval graphs in polynomial time. Journal of discrete algorithms, 14, 173-188. https://doi.org/10.1016/j.jda.2011.12.004

• Journal Article Type: Article
• Publication Date: Jul 1, 2012
• Deposit Date: Mar 11, 2013
• Publicly Available Date: Apr 17, 2013
• Journal: Journal of Discrete Algorithms
• Print ISSN: 1570-8667
• Electronic ISSN: 1570-8675
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 14
• Pages: 173-188
• DOI: https://doi.org/10.1016/j.jda.2011.12.004
• Keywords: Role assignment, Locally surjective homomorphism, Proper interval graph.
• Public URL: https://durham-repository.worktribe.com/output/1466778