On the Fine-Grained Complexity of Rainbow Coloring
Łukasz Kowalik, Juho Lauri, Arkadiusz Socała · SIAM Journal on Discrete Mathematics · 2018
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 the exponential time hypothesis fails. Motivated by this negative result we consider two parameterized variants of the problem. In the Subset Rainbow $k$-Coloring problem, introduced by Chakraborty et al. [ J. Comb. Optim., 21 (2009), pp. 330--347], 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 fixed parameter tractable (FPT) when parameterized by $|S|$. We also study the 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$, extending the result of Ananth, Nasre, and Sarpatwar, in FSTTCS, LIPIcs, Schloss Dagstuhl--Leibniz-Zentum für Informatik, Dagstuhl, Germany, 2011, pp. 241--251. We believe that our techniques used for the lower bounds may shed some light on the complexity of the classical Edge Coloring problem, where it is a major open question if a $2^{O(n)}$-time algorithm exists.