Fine-grained complexity of rainbow coloring and its variants

For a graph G and cR:E(G)→[k], a path P between u,v∈V(G) is a rainbow path if for distinct e,e′∈E(P), we have cR(e)≠cR(e′). RAINBOW k-COLORING takes a graph G and the objective is to check if there is cR:E(G)→[k] such that for all u,v∈V(G) there is a rainbow path between u and v. Two variants of the above problem are SUBSET RAINBOW k-COLORING and STEINER RAINBOW k-COLORING, where we are additionally given a subset S⊆V(G)×V(G) and S′⊆V(G), respectively. Moreover, the objective is to check if there is cR:E(G)→[k], such that there is a rainbow path for each (u,v)∈S and u,v∈S′, respectively. Under ETH, we obtain that for each k≥3: 1. RAINBOW k-COLORING has no 2o(|E(G)|)nO(1)-time algorithm. 2. STEINER RAINBOW k-COLORING has no 2o(|S|2)nO(1)-time algorithm. We also obtain that SUBSET RAINBOW k-COLORING and STEINER RAINBOW k-COLORING admit 2O(|S|)nO(1)- and 2O(|S|2)nO(1)-time algorithms, respectively.