Computing role assignments of proper interval graphs in polynomial time

详细信息	查看全文 | 推荐本文 |

• 作者：Pinar Heggernes^a ; ^{pinar.heggernes@ii.uib.no} ; Pim van 始t Hof^a ; ^{pim.vanthof@ii.uib.no} ; Danië ; l Paulusma^b ; ^{daniel.paulusma@durham.ac.uk}
• 关键词：Role assignment ; Locally surjective homomorphism ; Proper interval graph
• 刊名：Journal of Discrete Algorithms
• 出版年：2012
• 期刊代码：10_15708667
• 类别：mt
• 出版时间：July, 2012
• 卷：14
• 期：Complete
• 页码：173-188
• 文件大小：385 K

摘要

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 -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.