ON THE COMPUTATIONAL COMPLEXITY ASPECTS OF PERFECT ROMAN DOMINATION
نویسندگان
1 Department of Mathematics, Shahed University, Tehran, Iran.
2 Department of Mathematics, Shahed University, Tehran, Iran.
doi
10.22044/jas.2021.11146.1554چکیده
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 [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.
