Further Hardness Results on Rainbow and Strong Rainbow Connectivity

Abstract

A path in an edge-colored graph is \textit{rainbow} if no two edges of it are colored the same. The graph is said to be \textit{rainbow connected} if there is a rainbow path between every pair of vertices. If there is a rainbow shortest path between every pair of vertices, the graph is \textit{strong rainbow connected}. We consider the complexity of the problem of deciding if a given edge-colored graph is rainbow or strong rainbow connected. These problems are called \textsc{Rainbow connectivity} and \textsc{Strong rainbow connectivity}, respectively. We prove both problems remain $\NP$\hyp{}complete on interval outerplanar graphs and $k$-regular graphs for $k\ge 3$. Previously, no graph class was known where the complexity of the two problems would differ. We show that for block graphs, which form a subclass of chordal graphs, \textsc{Rainbow connectivity} is $\NP$\hyp{}complete while \textsc{Strong rainbow connectivity} is in $\P$. We conclude by considering some tractable special cases, and show for instance that both problems are in $\XP$ when parameterized by tree-depth.

13 pages, 4 figures

References in corpus (2)

• Note on the complexity of deciding the rainbow connectedness for bipartite graphs
• Rainbow connections for planar graphs and line graphs

Cited by in corpus (4)

• Computing Minimum Rainbow and Strong Rainbow Colorings of Block Graphs
• Complexity of Rainbow Vertex Connectivity Problems for Restricted Graph Classes
• A Polynomial Time Algorithm for Computing the Strong Rainbow Connection Numbers of Odd Cacti
• On the complexity of k-rainbow cycle colouring problems