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~~f(v)=i\, for i∈ \0,1,2\. The total weight of f is equal to ∑v∈ V f(v), and is denoted as $w(f)$. The Independent Roman Domination Number of G, denoted by iR(G), is defined as min(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.