New Hardness Results in Rainbow Connectivity

Abstract

A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph is (strongly) rainbow connected if there exists a (geodesic) rainbow path between every pair of vertices. The (strong) rainbow connectivity of a graph $G$, denoted by ($src(G)$, respectively) $rc(G)$ is the smallest number of colors required to edge color the graph such that the graph is (strong) rainbow connected. It is known that for \emph{even} $k$ to decide whether the rainbow connectivity of a graph is at most $k$ or not is NP-hard. It was conjectured that for all $k$, to decide whether $rc(G)\le k$ is NP-hard. In this paper we prove this conjecture. We also show that it is NP-hard to decide whether $src(G)\le k$ or not even when $G$ is a bipartite graph.

15 pages, 2 figures

References in corpus (5)

• Rainbow Connection Number and Connected Dominating Sets
• Rainbow Connection Number and Radius
• Rainbow connection of graphs with diameter 2
• Hardness and Algorithms for Rainbow Connection
• The complexity of determining the rainbow vertex-connection of graphs

Cited by in corpus (8)

• Note on the complexity of deciding the rainbow connectedness for bipartite graphs
• Rainbow connections for planar graphs and line graphs
• Upper bound for the rainbow connection number of bridgeless graphs with diameter 3
• Conflict-free connections: algorithm and complexity
• Further hardness results on the rainbow vertex-connection number of graphs
• Hardness result for the total rainbow $k$-connection of graphs
• Strong rainbow connection numbers of toroidal meshes
• A Polynomial Time Algorithm for Computing the Strong Rainbow Connection Numbers of Odd Cacti