Algorithmic aspects of the independent 2-rainbow domination number and independent Roman \{2\}-domination number

A 2-rainbow dominating function (2RDF) of a graph G is a function g from the vertex set V (G) to the family of all subsets of {1, 2} such that for each vertex v with g(v) = ∅ we have ⋃ u∈N(v) g(u) = {1, 2}. The minimum of g(V (G)) = ∑ v∈V (G) |g(v)| over all such functions is called the 2-rainbow domination number. A 2RDF g of a graph G is independent if no two vertices assigned non empty sets are adjacent. The independent 2-rainbow domination number is the minimum weight of an independent 2RDF of G. A Roman {2}-dominating function (R2DF) f : V −→ {0, 1, 2} of a graph G = (V,E) has the property that for every vertex v ∈ V with f(v) = 0 either there is u ∈ N(v) with f(u) = 2 or there are x, y ∈ N(v) with f(x) = f(y) = 1. The weight of f is the sum f(V ) = ∑ v∈V f(v). An R2DF f is called independent if no two vertices assigned non-zero values are adjacent. The independent Roman {2}-domination number is the minimum weight of an independent R2DF on G. We first show that the decision problem for computing the independent 2rainbow (respectively, independent Roman {2}-domination) number is NPcomplete even when restricted to planar graphs. Then, we give a linear algorithm that computes the independent 2-rainbow domination number as well as the independent Roman {2}-domination number of a given tree, answering problems posed in [M. Chellali and N. Jafari Rad, Independent 2-rainbow domination in graphs, J. Combin. Math. Combin. Comput. 94 2 A. Poureidi and N. Jafari Rad (2015) 133–148] and [A. Rahmouni and M. Chellali, Independent Roman {2}domination in graphs, Discrete Appl. Math. 236 (2018) 408–414]. Then, we give a linear algorithm that computes the independent 2-rainbow domination number of a given unicyclic graph.