  The Rainbow k-Coloring problem asks whether the edges of a given graph can be
colored in $k$ colors so that every pair of vertices is connected by a rainbow
path, i.e., a path with all edges of different colors. Our main result states
that for any $k\ge 2$, there is no algorithm for Rainbow k-Coloring running in
time $2^{o(n^{3/2})}$, unless ETH fails.
  Motivated by this negative result we consider two parameterized variants of
the problem. In Subset Rainbow k-Coloring problem, introduced by Chakraborty et
al. [STACS 2009, J. Comb. Opt. 2009], we are additionally given a set $S$ of
pairs of vertices and we ask if there is a coloring in which all the pairs in
$S$ are connected by rainbow paths. We show that Subset Rainbow k-Coloring is
FPT when parameterized by $|S|$. We also study Maximum Rainbow k-Coloring
problem, where we are additionally given an integer $q$ and we ask if there is
a coloring in which at least $q$ anti-edges are connected by rainbow paths. We
show that the problem is FPT when parameterized by $q$ and has a kernel of size
$O(q)$ for every $k\ge 2$ (thus proving that the problem is FPT), extending the
result of Ananth et al. [FSTTCS 2011].
