Complexity of rainbow vertex connectivity problems for restricted graph classes

详细信息    查看全文

• 作者：Juho Lauri ^{juho.lauri@tut.fi}
• 关键词：Rainbow connectivity ; Computational complexity
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：11 March 2017
• 年：2017
• 卷：219
• 期：Complete
• 页码：132-146
• 全文大小：634 K
• 卷排序：219

文摘

A path in a vertex-colored graph GG is vertex rainbow   if all of its internal vertices have a distinct color. The graph GG is said to be rainbow vertex connected   if there is a vertex rainbow path between every pair of its vertices. Similarly, the graph GG is strongly rainbow vertex connected if there is a shortest path which is vertex rainbow between every pair of its vertices. We consider the complexity of deciding if a given vertex-colored graph is rainbow or strongly rainbow vertex connected. We call these problems Rainbow Vertex Connectivity and Strong Rainbow Vertex Connectivity, respectively. We prove both problems remain NP-complete on very restricted graph classes including bipartite planar graphs of maximum degree 3, interval graphs, and kk-regular graphs for k≥3k≥3. We settle precisely the complexity of both problems from the viewpoint of two width parameters: pathwidth and tree-depth. More precisely, we show both problems remain NP-complete for bounded pathwidth graphs, while being fixed-parameter tractable parameterized by tree-depth. Moreover, we show both problems are solvable in polynomial time for block graphs, while Strong Rainbow Vertex Connectivity is tractable for cactus graphs and split graphs.