On the computational complexity of Roman $$\{2\}$$ { 2 } -domination in grid graphs

A Roman $$\{2\}$$ { 2 } -dominating function of a graph $$G=(V,E)$$ G = ( V , E ) is a function $$f:V\rightarrow \{0,1,2\}$$ f : V → { 0 , 1 , 2 } such that every vertex $$x\in V$$ x ∈ V with $$f(x)=0$$ f ( x ) = 0 either there exists at least one vertex $$y\in N(x)$$ y ∈ N ( x ) with $$f(y)=2$$ f ( y ) = 2 or there are at least two vertices $$u,v\in N(x)$$ u , v ∈ N ( x ) with $$f(u)=f(v)=1$$ f ( u ) = f ( v ) = 1 . The weight of a Roman $$\{2\}$$ { 2 } -dominating function f on G is defined to be the value of $$\sum _{x\in V} f(x)$$ ∑ x ∈ V f ( x ) . The minimum weight of a Roman $$\{2\}$$ { 2 } -dominating function on G is called the Roman $$\{2\}$$ { 2 } -domination number of G. In this paper, we prove that the decision problem associated with Roman $$\{2\}$$ { 2 } -domination number is NP-complete even when restricted to subgraphs of grid graphs. Additionally, we answer an open question about the approximation hardness of Roman $$\{2\}$$ { 2 } -domination problem for bounded degree graphs.