On the Fine-Grained Complexity of Rainbow Coloring

Speaker(s)

Łukasz Kowalik

Date

Nov. 3, 2016, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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.

---