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 \{۰,۱,۲\} satisfying the condition that every vertex u with f(u) = ۰ is adjacent to exactly one vertex v for which f(v) = ۲‎. ‎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‎. ‎۱۴(۲۰۲۰)‎, ‎۳۴۲--۳۵۱]‎, ‎and using a similar argument‎, ‎show that MPRDP is APX-hard for graphs with bounded degree ۴‎.‎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‎.

کلیدواژه ها:

Dominating set‎ ، ‎perfect dominating set‎ ، ‎Roman dominating function‎ ، ‎perfect Roman dominating function‎ ، ‎APX-hard