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 [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.
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.