ON THE COMPUTATIONAL COMPLEXITY ASPECTS OF PERFECT ROMAN DOMINATION

‎A perfect Roman dominating function (PRDF) on a graph G is a function f : V (G) ! f0; 1; 2g such 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 [Bulletin Iran. 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 for star convex bipartite graphs, and it is solvable in linear time for bounded tree-width graphs. We also show that the perfect domination problem and perfect Roman omination problem are not equivalent in computational complexity aspects. Finally we propose an integer linear programming formulation for MPRDP.