Algorithmic aspects of Roman domination in graphs

For a simple, undirected graph G = (V, E), a Roman dominating function (RDF) f :V -> {0, 1, 2} has the property that, every vertex u with f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2. The weight of a RDF is the sum f (V) = Sigma(v is an element of V) f (v). The minimum weight of a RDF is called the Roman domination number and is denoted by (gamma R)(G). Given a graph G and a positive integer k, the Roman domination problem (RDP) is to check whether G has a RDF of weight at most k. The RDP is known to be NP-complete for bipartite graphs. We strengthen this result by showing that this problem remains NP-complete for two subclasses of bipartite graphs namely, star convex bipartite graphs and comb convex bipartite graphs. We show that (gamma R)(G) is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs, a subclass of split graphs. The minimum Roman domination problem (MRDP) is to find a RDF of minimum weight in the input graph. We show that the MRDP for star convex bipartite graphs and comb convex bipartite graphs cannot be approximated within (1 - epsilon) ln |V| for any epsilon > 0 unless NP subset of DT IME(|V|(O(log log |V|))) and also propose a 2(1+ ln(Delta + 1))-approximation algorithm for theMRDP, where Delta is the maximum degree of G. Finally, we show that the MRDP is APX-complete for graphs with maximum degree 5.