E. Eiben, R. Ganian, J. Laurila:

"On the Complexity of Rainbow Coloring Problems";

Discrete Applied Mathematics,246(2018), 38 - 48.

An edge-colored graph G is said to be rainbow connected if between each pair of vertices

there exists a path which uses each color at most once. The rainbow connection number,

denoted by rc(G), is the minimum number of colors needed to make G rainbow connected.

Along with its variants, which consider vertex colorings and/or so-called strong colorings,

the rainbow connection number has been studied from both the algorithmic and graphtheoretic

points of view.

In this paper we present a range of new results on the computational complexity of

computing the four major variants of the rainbow connection number. In particular, we

prove that the Strong Rainbow Vertex Coloring problem is NP-complete even on graphs

of diameter 3, and also when the number of colors is restricted to 2. On the other hand,

we show that if the number of colors is fixed then all of the considered problems can be

solved in linear time on graphs of bounded treewidth. Moreover, we provide a linear-time

algorithm which decides whether it is possible to obtain a rainbow coloring by saving a

fixed number of colors from a trivial upper bound. Finally, we give a linear-time algorithm

for computing the exact rainbow connection numbers for three variants of the problem on

graphs of bounded vertex cover number.

http://dx.doi.org/10.1016/j.dam.2016.10.021

https://publik.tuwien.ac.at/files/publik_276171.pdf

Created from the Publication Database of the Vienna University of Technology.