Abstract
The Rainbow kColoring 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 >= 2, there is no algorithm for Rainbow kColoring 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 Rainbow kColoring problem, introduced by Chakraborty 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 Rainbow kColoring is FPT when parameterized by S. We also study Subset Rainbow kColoring problem, where we are additionally given an integer q and we ask if there is a coloring in which at least q antiedges 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 >= 2, extending the result of Ananth et al. [FSTTCS 2011]. 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.
BibTeX  Entry
@InProceedings{kowalik_et_al:LIPIcs:2016:6400,
author = {Lukasz Kowalik and Juho Lauri and Arkadiusz Socala},
title = {{On the FineGrained Complexity of Rainbow Coloring}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {58:158:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6400},
URN = {urn:nbn:de:0030drops64001},
doi = {10.4230/LIPIcs.ESA.2016.58},
annote = {Keywords: graph coloring, computational complexity, lower bounds, exponential time hypothesis, FPT algorithms}
}
Keywords: 

graph coloring, computational complexity, lower bounds, exponential time hypothesis, FPT algorithms 
Collection: 

24th Annual European Symposium on Algorithms (ESA 2016) 
Issue Date: 

2016 
Date of publication: 

18.08.2016 