On the Fine-Grained Complexity of Rainbow Coloring

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. Even for k=2, the best known algorithm runs in 2^{n^2} time. Our main result states that for any k >= 2, there is no algorithm for Rainbow k-Coloring running in time 2^{o(n^{3/2})}, unless Exponential Time Hypothesis fails. I will give an overview of the reduction and discuss some open problems.