On the fine-grained complexity of rainbow coloring
17 July 2018
The k-RC 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 $kge 2$, there is no algorithm for k-RC 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 the Subset k-RC problem, introduced by Chakraborty emph{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 k-RC is FPT when parameterized by $|S|$. We also study Maximum k-RC 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 $kge 2$, extending the result of Ananth emph{et al.}~[FSTTCS 2011]. We believe that our techniques used for the lower bounds may shed some light on the complexity of the classical {sc Edge Coloring} problem, where it is a major open question if a $2^{O(n)}$-time algorithm exists.
