Perfect Italian domination on some generalizations of cographs (Q6616154)

The motivation for this study is rooted in deploying defensive forces optimally to safeguard multiple points of importance. Similar scenarios from various historical periods have been described by \textit{C. S. ReVelle} and \textit{K. E. Rosing} [Am. Math. Mon. 107, No. 7, 585--594 (2000; Zbl 1039.90038)].\N\N``Given a graph \(G = (V, E)\), the Perfect Italian domination function is a mapping \(f: V\rightarrow\{0, 1, 2\}\) such that for any vertex \(v\in V\) with \(f(v)\) equals zero, \( \sum_{u\in N(v)}f(u)\) must be two. In simpler terms, for each vertex \(v\) labeled zero, one of the following conditions must be satisfied: \N\N(1) exactly two neighbours of \(v\) are labeled 1, and every other neighbour of \(v\) is labeled zero, \N\N(2) exactly one neighbour of \(v\) is labeled 2, and every other neighbour of \(v\) is labeled zero. \N\NThe weight of the function \(f\) is calculated as the sum of \(f(u)\) over all \(u\in V\).'' \N\NThis paper focusses on the MIN-PID problem.\N\N``The Perfect Italian domination problem involves finding a Perfect Italian domination function that minimizes the weight. We have devised a linear-time algorithm to solve this problem for \(P_4\)-sparse graphs, which represent well-established generalization of cographs. Furthermore, we have proved that the problem is efficiently solvable for distance-hereditary graphs. We have also shown that the decision version of the problem is NP-complete for 5-regular graphs and comb convex bipartite graphs.''\N\NIn the conclusion, the authors mention important issues:\N\N``It would be intriguing to explore the complexity of the problem for AT-free graphs or related subclasses, such as permutation graphs. Notably, the complexity status of the problem for subclasses of bipartite graphs, like chordal bipartite and convex bipartite graphs, remains unknown, thus presenting promising avenues for future research.''\N\NIt is an interesting work on the domination problem and the usefulness of NP-completeness.