Generalized rainbow connectivity of graphs

Let C={c1,c2,…,ck}C={c1,c2,…,ck} be a set of k   colors, and let ℓ→=(ℓ1,ℓ2,…,ℓk) be a k  -tuple of nonnegative integers ℓ1,ℓ2,…,ℓkℓ1,ℓ2,…,ℓk. For a graph G=(V,E)G=(V,E), let f:E→Cf:E→C be an edge-coloring of G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f   is ℓ→-rainbow connected if every two vertices of G have a path P connecting them such that the number of edges on P   that are colored with cjcj is at most ℓjℓj for each index j∈{1,2,…,k}j∈{1,2,…,k}. Given a k  -tuple ℓ→ and an edge-colored graph, we study the problem of determining whether the edge-colored graph is ℓ→-rainbow connected. In this paper, we first study the computational complexity of the problem with regard to certain graph classes: the problem is NP-complete even for cacti, while is solvable in polynomial time for trees. We then give an FPT algorithm for general graphs when parameterized by both k   and ℓmax=max⁡{ℓj|1⩽j⩽k}ℓmax=max⁡{ℓj|1⩽j⩽k}.