Perfect Italian domination in graphs: complexity and algorithms (Q2161253)

Let \(G\) be a graph. A map \(f:V(G)\rightarrow\{0,1,2\}\) is called a perfect Italian dominating function if \(\sum_{u\in N_G(v)}{f(u)}=2\) for every vertex \(v\) with \(f(v)=0\). The minimum weight \(\sum_{v\in V(G)}{f(v)}\) among all perfect Italian dominating functions is the perfect Italian domination number and the problem to obtain it is denoted by MIN-PIDF. This work considers MIN-PIDF from an algorithmic perspective. It is shown that the problem is polynomially solvable for block graphs and series-parallel graphs. On the other side, the MIN-PIDF problem is NP-hard for chordal graphs, and the approximation harness is discussed in the general case. The complexity difference of MIN-PIDF with respect to the ordinary Italian domination function (where in the condition \(=2\) is replaced by \(\geq 2\)) is also considered.