Shahed University

ON THE COMPUTATIONAL COMPLEXITY ASPECTS OF PERFECT ROMAN DOMINATION

Nader Jafari Rad | میر حسینی
URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=169873
Date :  2022/10/09
Publish in :    Journal of Algebraic Systems

Link :  https://jas.shahroodut.ac.ir/article_2469.html
Keywords :perfect Roman dominating functionو‎ ‎APX-hard

Abstract :
A perfect Roman dominating function (PRDF) on a graph G is a function f:V(G)→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‎.