Roman {3}-domination in graphs: Complexity and algorithms

A Roman {3}-dominating function on a graph G is a function f : V(G) -> {0, 1, 2, 3} having the property that for any vertex u E V(G), if f (u) = 0, then & sum; f (u) = 1, then & sum;(vENG(u))f(v) >= 3, and if the sum f(V(G)) = & sum; (vENG(u))f(v) >= 2. The weight of a Roman {3}-dominating function f is v(EV(G))f(v) and the minimum weight of a Roman {3}-dominating function on G is called the Roman {3}-domination number of G and is denoted by gamma({R3})(G). Given a graph G, ROMAN {3}-DOMINATION asks to find the minimum weight of a Roman {3}-dominating function on G. In this paper, we study the algorithmic aspects of ROMAN {3}-DOMINATION on various graph classes. We show that the decision version of ROMAN {3}-DOMINATION remains NP-complete for chordal bipartite graphs, planar graphs, starconvex bipartite graphs, and chordal graphs. We show that ROMAN {3}-DOMINATION cannot be approximated within a ratio of (1/3 - epsilon)ln |V(G)| for any epsilon > 0 unless P = NP for bipartite graphs as well as chordal graphs, whereas ROMAN {3}-DOMINATION can be approximated within a factor of O(ln triangle) for graphs having maximum degree triangle. We also show that ROMAN {3}-DOMINATION is APX-complete for graphs with maximum degree 4. On the positive side, we show that ROMAN {3}-DOMINATION can be solved in linear time for chain graphs and cographs. (c) 2022 Elsevier B.V. All rights reserved.