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)to {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 [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 even when restricted to star convex bipartite graphs‎. ‎Moreover‎, ‎we show that MPRDP is solvable in linear time for bounded tree-width‎‎graphs‎. ‎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‎.