Agrawal, Akanksha
FineGrained Complexity of Rainbow Coloring and its Variants
Abstract
Consider a graph G and an edgecoloring c_R:E(G) \rightarrow [k]. A rainbow path between u,v \in V(G) is a path P from u to v such that for all e,e' \in E(P), where e \neq e' we have c_R(e) \neq c_R(e'). In the Rainbow kColoring problem we are given a graph G, and the objective is to decide if there exists c_R: E(G) \rightarrow [k] such that for all u,v \in V(G) there is a rainbow path between u and v in G. Several variants of Rainbow kColoring have been studied, two of which are defined as follows. The Subset Rainbow kColoring takes as an input a graph G and a set S \subseteq V(G) \times V(G), and the objective is to decide if there exists c_R: E(G) \rightarrow [k] such that for all (u,v) \in S there is a rainbow path between u and v in G. The problem Steiner Rainbow kColoring takes as an input a graph G and a set S \subseteq V(G), and the objective is to decide if there exists c_R: E(G) \rightarrow [k] such that for all u,v \in S there is a rainbow path between u and v in G. In an attempt to resolve open problems posed by Kowalik et al. (ESA 2016), we obtain the following results.
 For every k \geq 3, Rainbow kColoring does not admit an algorithm running in time 2^{o(E(G))}n^{O(1)}, unless ETH fails.
 For every k \geq 3, Steiner Rainbow kColoring does not admit an algorithm running in time 2^{o(S^2)}n^{O(1)}, unless ETH fails.
 Subset Rainbow kColoring admits an algorithm running in time 2^{\OO(S)}n^{O(1)}. This also implies an algorithm running in time 2^{o(S^2)}n^{O(1)} for Steiner Rainbow kColoring, which matches the lower bound we obtain.
BibTeX  Entry
@InProceedings{agrawal:LIPIcs:2017:8099,
author = {Akanksha Agrawal},
title = {{FineGrained Complexity of Rainbow Coloring and its Variants}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {60:160:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8099},
URN = {urn:nbn:de:0030drops80990},
doi = {10.4230/LIPIcs.MFCS.2017.60},
annote = {Keywords: Rainbow Coloring, Lower bound, ETH, Finegrained Complexity}
}
01.12.2017
Keywords: 

Rainbow Coloring, Lower bound, ETH, Finegrained Complexity 
Seminar: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Issue date: 

2017 
Date of publication: 

01.12.2017 