Fine-grained complexity of rainbow coloring and its variants (Q2051859)

Let \(G\) be a graph and \(c_R : E(G) \rightarrow [k]\) be an edge-coloring of \(G\). 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 \(k\)-Coloring problem for a given graph \(G\) the objective is to decide if there exists an edge-coloring \(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\). Two variants of the above problem are Subset Rainbow \(k\)-Coloring and Steiner Rainbow \(k\)-Coloring, where for a given subset \(S \subseteq V (G) \times V (G)\) respectively \(S' \subseteq V (G)\) the objective is to check if there is \(c_R : E(G) \rightarrow [k]\) such that there is a rainbow path for each \((u, v) \in S\) respectively \(u, v \in S'\). In this paper it is proved that for all \(k \geq 3\), Rainbow \(k\)-Coloring does not admit an algorithm running in time \(2^{o(|E(G)|)}n^{\mathcal{O}(1)}\) unless ETH (Exponential Time Hypothesis) fails. This (partially) solves a conjecture of \textit{Ł. Kowalik} et al. [LIPIcs -- Leibniz Int. Proc. Inform. 57, Article 58, 16 p. (2016; Zbl 1397.68102)]. The author also studies the problem Steiner Rainbow \(k\)-Coloring and proves that for every \(k \geq 3\) the problem does not admit an algorithm running in time \(2^{o(|S|^2)}n^{\mathcal{O}(1)}\) unless ETH fails. She also obtains that for each \(k\geq 3\), Subset Rainbow \(k\)-Coloring and Steiner Rainbow \(k\)-Coloring admit \(2^{\mathcal{O}(|S|)}n^{\mathcal{O}(1)}\)- and \(2^{\mathcal{O}(|S|^{2})}n^{\mathcal{O}(1)}\)-time algorithms, respectively. Three open directions of study conclude the paper.