On the Fine-Grained Complexity of Rainbow Coloring

Prelegent(ci)

Łukasz Kowalik

Termin

3 listopada 2016 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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.

---