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.