A perfect Roman dominating function (PRDF) on a graph G is a function f: V (G) \0, 1, 2\ satisfying the condition that every vertex u with f (u) = 0 is adjacent to exactly one vertex v for which f (v) = 2. The weight of a PRDF f is the sum of the weights of the vertices under f. The perfect Roman domination number of G is the minimum weight of a PRDF in G. In this paper we study algorithmic and computational complexity aspects of the minimum perfect Roman domination problem (MPRDP) . We first correct the proof of a result published in BulletinIran. Math. Soc. 14 (2020) , 342--351, and using a similar argument, show that MPRDP is APX-hard for graphs with bounded degree 4. We prove that the decision problem associated to MPRDP is NP-complete even when restricted to star convex bipartite graphs. Moreover, we show that MPRDP is solvable in linear time for bounded tree-widthgraphs. We also show that the perfect domination problem and perfect Roman domination problem are not equivalent in computational complexity aspects. Finally we propose an integer linear programming formulation for MPRDP.
Mirhoseini et al. (Sun,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: