Complexity of rainbow vertex connectivity problems for restricted graph classes

DOI10.1016/J.DAM.2016.11.023MaRDI QIDQ505435zbMATH OpenOpenAlexFDO

Authors Juho Lauri

Publication date 23 January 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.07768

zbMATH Keywords

computational complexityrainbow connectivity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A path in a vertex-colored graph $G$ is emph{vertex rainbow} if all of its internal vertices have a distinct color. The graph $G$ is said to be emph{rainbow vertex connected} if there is a vertex rainbow path between every pair of its vertices. Similarly, the graph $G$ is emph{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 probRvc and probSrvc, respectively. We prove both problems remain NP-complete on very restricted graph classes including bipartite planar graphs of maximum degree 3, interval graphs, and $k$-regular graphs for $kgeq3$. 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 probSrvc is tractable for cactus graphs and split graphs.

Recommendations

• Further hardness results on rainbow and strong rainbow connectivity
• Rainbow vertex coloring bipartite graphs and chordal graphs
• Algorithms for the rainbow vertex coloring problem on graph classes
• The complexity of determining the rainbow vertex-connection of a graph
• Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• A partial k-arboretum of graphs with bounded treewidth
• A simplified NP-complete satisfiability problem
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Bigeodetic graphs
• Fundamentals of parameterized complexity
• Further hardness results on rainbow and strong rainbow connectivity
• Further hardness results on the rainbow vertex-connection number of graphs
• Grad and classes with bounded expansion. I: Decompositions
• Hardness and algorithms for rainbow connection
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• New races in parameterized algorithmics
• On planar geodetic graphs
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• Parameterized algorithms
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Rainbow connection in graphs
• Rainbow connection in oriented graphs
• The complexity of determining the rainbow vertex-connection of a graph
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• The strong rainbow vertex-connection of graphs
• Topology of series-parallel networks

Cited in

(7)

• Further hardness results on the rainbow vertex-connection number of graphs
• Rainbow vertex coloring bipartite graphs and chordal graphs
• Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
• Hardness and Algorithms for Rainbow Connectivity
• The complexity of determining the rainbow vertex-connection of a graph
• Algorithms for the rainbow vertex coloring problem on graph classes
• Further hardness results on rainbow and strong rainbow connectivity

This page was built for publication: Complexity of rainbow vertex connectivity problems for restricted graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q505435)