Exploring Algorithmic Solutions for the Independent Roman Domination Problem in Graphs

Given a graph G= (V, E), a function f: V \0, 1, 2\ is said to be a Roman Dominating function if for every v V with f (v) =0, there exists a vertex u N (v) such that f (u) =2. A Roman Dominating function f is said to be an Independent Roman Dominating function (or IRDF), if V₁ V₂ forms an independent set, where Vᵢ=\v V~~f (v) =i\, for i \0, 1, 2\. The total weight of f is equal to ₕ ₕ f (v), and is denoted as w (f). The Independent Roman Domination Number of G, denoted by iR (G), is defined as min\w (f) ~~f is an IRDF of G\. For a given graph G, the problem of computing iR (G) is defined as the Minimum Independent Roman Domination problem. The problem is already known to be NP-hard for bipartite graphs. In this paper, we further study the algorithmic complexity of the problem. In this paper, we propose a polynomial-time algorithm to solve the Minimum Independent Roman Domination problem for distance-hereditary graphs, split graphs, and P₄-sparse graphs.