Algorithmic aspects of Roman domination in graphs

• Published in: Journal of applied mathematics & computing 2020-10, Vol.64 (1-2), p.89-102
• Main Authors: Padamutham, Chakradhar, Palagiri, Venkata Subba Reddy
• Format: Article
• Language: English
• Subjects: Algorithms; Applied mathematics; Chain scission; Codes; Computational Mathematics and Numerical Analysis; Graphs; Mathematical and Computational Engineering; Mathematical functions; Mathematics; Mathematics and Statistics; Mathematics of Computing; Minimum weight; Original Research; Theory of Computation
• ISSN: 1598-5865; 1865-2085
• DOI: 10.1007/s12190-020-01345-4

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 ) = ∑ v ∈ V f ( v ) . The minimum weight of a RDF is called the Roman domination number and is denoted by γ 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 γ 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 - ϵ ) ln | V | for any ϵ > 0 unless N P ⊆ D T I M E ( | V | O ( log log | V | ) ) and also propose a 2 ( 1 + ln ( Δ + 1 ) ) -approximation algorithm for the MRDP, where Δ is the maximum degree of G . Finally, we show that the MRDP is APX-complete for graphs with maximum degree 5.