Hardness and Algorithms for Rainbow Connection

Sourav Chakraborty, Eldar Fischer, Arie Matsliah +1

An edge-colored graph $G$ is {\em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {\em rainbow connection} of a connected graph…