On the k-rainbow domination in graphs with bounded tree-width

M. Alambardar Meybodi (Department of Applied Mathematics and Computer Science, Faculty of Mathematics and Statistics, University of Isfahan, Iran)
M. R. Hooshmandasl (Department of Computer Science, University of Mohaghegh Ardabili, Ardabil, Iran)
P. Sharifani (Institute for Research in Fundamental Sciences(IPM), Tehran, Iran)
Ali Shakiba (Department of Computer Science, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran.)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 9, No 2 (2021): Electronic Journal of Graph Theory and Applications

Given a positive integer k and a graph G = (V, E), a function f from V to the power set of Ik is called a k-rainbow function if for each vertex v ∈ V, f(v)=∅ implies ∪u ∈ N(v)f(u)=Ik where N(v) is the set of all neighbors of vertex v and Ik = {1, …, k}. Finding a k-rainbow function of minimum weight of ∑v ∈ V|f(v)|, which is called the k-rainbow domination problem, is known to be NP-complete for arbitrary graphs and values of k. In this paper, we propose a dynamic programming algorithm to solve the k-rainbow domination problem for graphs with bounded tree-width tw in ????((2k + 1+1)twn) time, where G has n vertices. Moreover, we also show that the same approach is applicable to solve the weighted k-rainbow domination problem with the same complexity. Therefore, both problems of k-rainbow and weighted k-rainbow domination belong to the class FPT, or fixed parameter tractable, with respect to tree-width. In addition to formally showing the correctness of our algorithms, we also implemented these algorithms to illustrate some examples.