Independent Roman Domination: The Complexity and Linear-Time Algorithm for Trees

Abstract

For a graph $G=(V,E)$, an independent Roman dominating function (IRDF) is a function $f:V\to \{0,1,2\}$ having the property that: (1) every vertex assigned a value of 0 is adjacent to at least one vertex assigned a value of 2, (2) there are no two adjacent vertices with positive assignments. The weight of an IRDF ($w\left(f\right)$) is the sum of assignments for all vertices. The minimum weight of an independent Roman dominating function on graph G is the independent Roman domination number, denoted by $i_R\left(G\right)$. In this paper, we prove that the decision problem of minimum IRDF is $NP$-complete for chordal bipartite graphs. Then, we research the difference in complexity between the decision problem of RDF and IRDF. Finally, we propose a linear-time algorithm for computing the minimum weight of an independent Roman dominating function in trees.

1. Introduction

In this paper, the independent Roman dominating function we have studied is a variant of the Roman dominating function.

Let G be a simple and undirected graph with sets of vertex $V\left(G\right)$ and edge $E\left(G\right)$. For every vertex $v\in V$, we denote the set $\{u\in V(G):uv\in E(G\left)\right\}$ is the open neighborhood $N\left(v\right)$ and the set $N\left(v\right)\cup \left\{v\right\}$ is the closed neighborhood $N\left[v\right]$. In graph G, the degree of a vertex v is denoted by $d_G\left(v\right)$, the minimum degree is denoted by $\delta =\delta \left(G\right)$ and the maximum degree is denoted by $\Delta =\Delta \left(G\right)$. If $d_G\left(u\right)=1$, then we call the vertex u is a leaf and its neighbor is a support vertex. If a support vertex is adjacent to at least two leaves, we call it a strong support vertex. If $V\left(G\right)$ can be partitioned into two disjoint independent sets, we call the graph G a bipartite graph. If every cycle of length at least 6 has a chord in bipartite graph G, then the bipartite graph G is called a chordal bipartite graph. A tree T is an acyclic connected graph. For any positive integer k, we denote the set $\{1,2,...,k\}$ by $\left[k\right]$. The dihedral group $D_n$ is the symmetry group of a regular polygon with n sides.

For a graph $G=(V,E)$, let $f:V\to \{0,1,2\}$ be a function, $V_i=\{v\in V:f\left(v\right)=i\}$ for $i=0,1,2$ be a set, and $(V_0,V_1,V_2)$ be the ordered partition of V induced by f. The functions $f:V\to \{0,1,2\}$ and the ordered partitions $(V_0,V_1,V_2)$ of V are a $1-1$ correspondence. So, we will write $f=(V_0,V_1,V_2)$.

The concept of Roman domination in graphs was introduced by Cockayne et al. in 2004 [1]. The definition of Roman dominating function is that a function $f:V\to \{0,1,2\}$ is a Roman dominating function (RDF) if every vertex assigned a value of 0 is adjacent to at least one vertex assigned a value of 2 [2]. The weight of an RDF is the sum of assignments for all vertices. The minimum weight of a Roman dominating function on G is the Roman domination number, denoted by ${\gamma }_R\left(G\right)$.

To date, many articles have been published on the topic of Roman domination. Cockayne et al. [2] introduced the properties of Roman dominating functions. Blidia, Chambers et al. [3,4,5,6] researched the bounds on Roman dominating functions and Bermudo et al. [7,8] discovered the relationships with some domination parameters. In terms of algorithm and complexity, Cockayne et al. [2] introduced a linear-time algorithm for computing Roman domination problem on trees. McRae [2] showed the decision problem corresponding to Roman dominating functions (DECIDE-RDF) was $NP$-complete for bipartite graphs, split graphs, and planar graphs. Moreover, some linear-time algorithms for the Roman domination problem on bounded treewidth graphs and block graphs were proposed [9]. Liedloff et al. [10] discovered that there were linear-time algorithms for computing the Roman domination number on cographs and interval graphs. Many variants of the Roman domination problem have also been studied in depth by many scholars [11,12,13,14].

The concept of the independent dominating set originated from the chessboard problems. The correlation theory was formalized by Berge [15] in 1962. A set S is independent if there are no connected edges for any two vertices in S. An independent dominating set of G is a set that is both dominating and independent in G. The independent domination number of G, denoted by $i_G$, is the minimum size of an independent dominating set.

Bound on the independent domination number was established by Berge [16]. Subsequently, the upper bound was improved by Blidia et al. [17]. Moreover, the research of independent dominating problem has also been extended to various special graph classes, for example, claw-free graph [18], bipartite graph [19], regular graph [20]. In terms of complexity, the independent domination problem is $NP$-complete even when restricted to bipartite graphs [21], to unit disk graphs [22], or to planar cubic graphs [23]. It was straightforward to calculate the independent domination number of a tree in linear-time [24]. Telle and Proskurowski [25] proved a polynomial-time algorithm for graphs of bounded treewidth and Farber [26] showed the linear-time algorithm of chordal graphs.

The independent Roman domination we studied in this paper is a variant of independent domination and Roman domination. An independent Roman dominating function (IRDF) is a function $f:V\to \{0,1,2\}$ having the property that: (1) every vertex assigned a value of 0 is adjacent to at least one vertex assigned a value of 2, (2) there are no two adjacent vertices with positive assignments. The weight of an IRDF ($w\left(f\right)$) is the sum of assignments for all vertices. The minimum weight of an independent Roman dominating function on graph G is the independent Roman domination number, denoted by $i_R\left(G\right)$.

1.1. Related Work

Cockayne et al. [2] put forward relevant concepts and conjectures, and proposed some open questions. Adabi et al. [27] studied the relations with independent domination, Roman domination and obtained some properties and bounds. Rad et al. [28] improved some previous bounds which were proposed by Adabi et al. [27]. Chellali et al. proposed a strong equivalence relationship between independent Roman domination numbers and Roman domination numbers on Trees [29]. In the private communication between Cockayne et al. and BMcRae [2], they proposed about the decision problem corresponding to independent Roman dominating functions is $NP$-complete, even when restricted to bipartite graphs. Wu et al. [30] conducted an in-depth study of independent Roman domination for stable and vertex-critical graphs.

1.2. Our Results

In this paper, we study the complexity and algorithmic aspects of independent Roman domination in graphs. Firstly, we show that the decision problem corresponding to independent Roman dominating functions (DECIDE-IRDF) is $NP$-complete, even when restricted to chordal bipartite graphs. Secondly, we discuss the complexity difference between DECIDE-RDF and DECIDE-IRDF by portraying a special graph class where one problem can be solved in polynomial time and the other is $NP$-complete. Finally, we present a linear-time algorithm for computing the independent Roman domination number in trees.

The rest of the paper is organized as follows. In Section 2, we show that the decision problem of IRDF is $NP$-complete for chordal bipartite graphs. In Section 3, we give a characterization of the difference in complexity between the decision problems of RDF and IRDF. In Section 4, we propose a linear-time algorithm for computing the independent Roman domination number in trees. In Section 5, we conclude the paper.

2. DECIDE-IRDF Is NP-Complete for Chordal Bipartite Graphs

In this section, we show that the decision problem of IRDF is $NP$-complete for chordal bipartite graphs. Firstly, the independent Roman domination problem ($IRD$) is an $NP$ problem, since we can check whether a function f is an IRDF and the weight of f at most k in polynomial time. Secondly, our goal is to transform any instance of $X3C$ into an instance G of $IRD$. Let $X=\{x_1,x_2,...,x_{3q}\}$ and $C=\{C_1,C_2,...,C_t\}$ be an arbitrary of $X3C$.

Construction 1.

For each corresponding $c_j$ in C, we build a circle $C_4$ with four sides and add an edge from any one vertex of $C_4$$\left(a_j\right)$ to $c_j$. Let $b_j,d_j,e_j$ be the another three vertices different from $a_j$ of $C_4$. Let $Y=\{c_1,c_2,...,c_t\}$. Now to obtain a graph G, we add edges $c_j{x}_i$ if $x_i\in C_j$ (see Figure 1). Set $k=3t+q$. Clearly, G is a chordal bipartite graph.

Lemma 1.

If the instance $X,C$ of $X3C$ has a solution $C^{\prime }$, there exists an independent Roman dominating function with weight $f\left(G\right)=3t+q$ in graph G.

Proof. 

Suppose that the instance $X,C$ of $X3C$ has a solution $C^{\prime }$. We construct an independent Roman dominating function f on G of weight k. For every $C_j$, assign the 2 to $c_j$ if $C_j\in C^{\prime }$ and 0 to $c_j$ if $C_j\notin C^{\prime }$. If we assign the 2 to $c_j$, let $f\left(a_j\right)=0$ and $f\left(d_j\right)=2$. If we assign the 0 to $c_j$, let $f\left(a_j\right)=2$ and $f\left(d_j\right)=1$. Finally, assign 0 to the remaining vertices of G. Since $C^{\prime }$ exists, its cardinality is precisely q, the number of $c_j$’s with value 2 is q, having disjoint neighborhoods in $\{x_1,x_2,...,x_{3q}\}$, where every $x_i$ has one neighbor be assigned 2. Hence, it is straightforward to see that f is an independent Roman dominating function with weight $f\left(G\right)=3t+q=k$.    □

Claim 1.

Let $H_j$ be the subgraph of G induced by the vertices of $\{a_j,b_j,c_j,d_j,e_j\}$, and let $f:V\to \{0,1,2\}$ be an IRDF on $H_j$ with minimum weight, then:

$$f\left(H_j\right)=\left\{\begin{array}{ccccc}& 3\hfill & & if\hfill & \hfill f\left(c_j\right)=0\\ & 4\hfill & & if\hfill & \hfill f\left(c_j\right)\ne 0\end{array}\right.$$

We give all the assignment possibilities of the subgraph $H_j$ on independent Roman dominating function f and show them in Figure 2 with symmetrical Figure 2 and Figure 3.

Claim 2.

For a graph G which has an independent Roman function f with weight at most k, the $c_j$ will not be assigned a value of 1.

Proof. 

We suppose that there exists a t satisfies $f\left(c_t\right)=1$. By Claim 1, this implies that $f\left(H_t\right)=4$. Now, we can define a new IRDF $g:V\to \{0,1,2\}$ as $g\left(c_t\right)=g\left(d_t\right)=2$, $g\left(a_t\right)=g\left(b_t\right)=0$ and $g\left(u\right)=f\left(u\right)$ otherwise. It is clear that g is an IRDF on graph G and $w\left(g\right)=w\left(f\right)$. Therefore, we can replace all cases where $c_j$ is assigned 1.    □

Claim 3.

For a graph G which has an independent Roman domination function f with weight at most k, $f\left(x_i\right)=0$.

Proof. 

Conversely, we suppose that $f\left(x_a\right)\ne 0$ for some $x_a\in X$. We have $f\left(x_a\right)\ge 1$, thus for each $c_a\in C$ which exists the edge with the $x_a$, let $f\left(c_a\right)=0$. By Claims 1 and 2, we know that if $f\left(c_a\right)=0$, we have $f\left(H_a\right)=3$ and if $f\left(c_a\right)=2$, we have $f\left(H_a\right)=4$. Then, we discuss the rest of the vertices in X except $x_a$.   □

Case 1. 

No vertex can be dominated by $c_j$ assigned to 2.

According the assumption, we know ${\sum }_{u\in N\left(x_i\right)}f\left(u\right)=0$ for each $x_i\in X$.

It implying that $f\left(x_i\right)>0$ for each $x_i\in X$ and $f\left(c_j\right)=0$ for each $c_j\in Y$.

Since $\mid X\mid =3q$, a contradiction we have $f\left(G\right)\ge 3q+3t>k$.

Case 2. 

There exist some vertices be dominated by $c_j$ assigned to 2. Considering the following subcases.

Subcase 2.1. 

Except for vertex $x_a$, the other vertices can be fully dominated by $c_j$ assigned to 2.

Hence, $f\left(x_i\right)=0$ for each $\{x_i:x_i\in X,x_i\ne x_a\}$.

The number of $f\left(c_j\right)=2$ equals $\lceil \frac{3q-1}{3}\rceil$.

When other vertices in Y are assigned a value of 0, the sum of the weights of graph G is the smallest.

We have $f\left(G\right)\ge \lceil \frac{3q-1}{3}\rceil *4+1+(t-\lceil \frac{3q-1}{3}\rceil )*3>3t+q$, this contradicts our known.

Subcase 2.2. 

There exist some vertices not be dominated by $c_j$ assigned to 2.

We assume m equals the number of vertices which $f\left(c_j\right)=2$ and we have $m<q$.

We let $n=3q-3m$ represent vertices in set X whose assignments are greater than 0.

Hence, $f\left(G\right)\ge n+4m+(t-m)*3$.

Combining these three formulas, we have a contradiction $f\left(G\right)>3t+q$.

Combining the above two situations, we prove that $f\left(x_i\right)=0$ for each $x_i\in X$.

Lemma 2.

If there exists an independent Roman dominating function with weight $f\left(G\right)=3t+q$ in graph G, the instance $X,C$ of $X3C$ has a solution $C^{\prime }$.

Proof. 

Suppose that G has an independent Roman function with weight at most k. Among all such functions let $f=(V_0,V_1,V_2)$. Clearly, by Claims 2 and 3, we have $f\left(c_j\right)=2$ or 0 for each $j\in \left[t\right]$ and $f\left(x_i\right)=0$ for each $i\in \left[3q\right]$.

Moreover, each $x_i$ is dominated by its adjacent $c_j$, so the number of vertices which $f\left(c_j\right)=2$ equals p and $p\ge \frac{3q}{3}=q$. Since $f\left(G\right)=4p+(t-p)*3\le 3t+q$, combining the above two inequalities, we have $p=q$. Consequently, $C^{\prime }=\{C_j:g\left(c_j\right)=2\}$ is an exact cover for C.

By Lemmas 1 and 2, we have reached the final conclusion.   □

Theorem 1.

The decision problem of IRDF is $NP$-complete for chordal bipartite graphs.

3. Complexity Difference between Roman Domination and Independent Roman Domination

Before that, many scholars have conducted in-depth research on the complexity of decision problems for different graph classes. However, from the overall perspective, we hope that through the research on the complexity differences, we can make more effective decisions when constructing models for practical problems in life.

Therefore, we want to find some special graph classes in which one problem is solvable in polynomial time, whereas the other one is $NP$-complete. Next, we describe the difference in complexity between Roman domination and independent Roman domination by defining two special graph classes $GR$ and $GIR$. On any $GR$ graph, the Roman domination problem is solvable in polynomial time and the independent Roman domination problem is $NP$-complete. However, on any $GIR$ graph, the independent Roman domination problem is solvable in polynomial time and the Roman domination problem is $NP$-complete.

Firstly, we define that $G^{\prime }$ is constructed from G, which means that the original vertices and edges on graph G are not changed, but only changed into $G^{\prime }$ by adding a specific structure.

Construction 2.

Let graph G have n vertices. For any vertex $v_i$ in graph G, we define some corresponding vertex sets and edge sets.

• $A_i=\{a_i^1,a_i^2\}$.
• $B_i=\{b_i^1,b_i^2,b_i^3\}$.
• $C_i=\{c_i^1,c_i^2,c_i^3,c_i^4,c_i^5\}$.
• $E_i^A=\left\{a_i^1{a}_i^2\right\}$
• $E_i^B=\{b_i^1{b}_i^2,b_i^2{b}_i^3,b_i^3{b}_i^1\}$
• $E_i^C=\{c_i^1{c}_i^2,c_i^1{c}_i^3,c_i^1{c}_i^4,c_i^1{c}_i^5\}$

(a) 

For any vertex $v_i$ in the graph G, add the set of vertices $A_i\bigcup B_i\bigcup C_i$.

(b) 

For any vertex $v_i$ in the graph G, add the set of edges $\left\{v_i{a}_i^1\right\}\bigcup E_i^A\bigcup \left\{a_i^1{b}_i^1\right\}\bigcup E_i^B\bigcup \left\{b_i^1{c}_i^1\right\}\bigcup E_i^C$.

On the basis of graph G, the new graph formed according to the above construction methods is called $GIR$ graph. See Figure 3.

Lemma 3.

Let $G^{\prime }=(V^{\prime },E^{\prime })$ be a $GIR$ graph which is constructed from graph $G=(V,E)$, we have $i_R\left(G^{\prime }\right)=6n$.

Proof. 

For any vertex $v_i\in V$, let $H_i$ be a subgraph of $G^{\prime }$ which is induced by the set of vertices $(\left\{v_i\right\}\cup A_i\cup B_i\cup C_i)$. It is clear that for any IRDF f of $G^{\prime }$, we have ${\sum }_{u\in V\left(H_i\right)}f\left(u\right)\ge 6$. Therefore we can infer that $i_R\left(G^{\prime }\right)\ge 6n$. Let a function $g:V^{\prime }\to \{0,1,2\}$ with the property that for each $i⩽n$, $g\left(a_i^1\right)=g\left(b_i^2\right)=g\left(c_i^1\right)=2$ and $g\left(u\right)=0$ otherwise. It is clear that g is an IRDF on $G^{\prime }$ and $w\left(g\right)=6n$. So we have $i_R\left(G^{\prime }\right)\le 6n$. This implies that $i_R\left(G^{\prime }\right)=6n$.   □

Lemma 4.

Let $G^{\prime }=(V^{\prime },E^{\prime })$ be a $GIR$ graph which is constructed from graph $G=(V,E)$. Then, graph G has a Roman domination function where the weight at most k if and only if $GIR$ graph $G^{\prime }$ has a Roman domination function where the weight at most $k+5n$.

Proof. 

(Necessity:) Since G has a Roman domination function $f:V\left(G\right)\to \{0,1,2\}$ with weight at most k, we can define $f^{\prime }:V^{\prime }\left(G^{\prime }\right)\to \{0,1,2\}$ as follows: for each $i⩽n$,

• $f^{\prime }\left(a_i^2\right)=1$, $f^{\prime }\left(b_i^1\right)=f^{\prime }\left(c_i^1\right)=2$.
• $f^{\prime }\left(v_i\right)=f\left(v_i\right)$.
• $f^{\prime }\left(u\right)=0$ otherwise.

It is clear that $f^{\prime }$ is a Roman domination function on $G^{\prime }$, and the weight of $f^{\prime }$ at most $k+5n$.

(Sufficiency:) We assume that function $g^{\prime }:V^{\prime }\left(G^{\prime }\right)\to \{0,1,2\}$ is a Roman domination function on $G^{\prime }$ with minimum weight and $w\left(g^{\prime }\right)⩽k+5n$.    □

Claim 4.

$g^{\prime }\left(c_i^1\right)=2$ for each $i⩽n$.

Proof. 

We suppose that there exists a t satisfying $g^{\prime }\left(c_t^1\right)<2$. We have $g^{\prime }\left(c_t^2\right)+g^{\prime }\left(c_t^3\right)+g^{\prime }\left(c_t^4\right)+g^{\prime }\left(c_t^5\right)\ge 4$. Now, we can define a new RDF $g^{″}:V^{\prime }\left(G^{\prime }\right)\to \{0,1,2\}$ as $g^{″}\left(c_t^1\right)=2$, $g^{″}\left(c_t^2\right)=g^{″}\left(c_t^3\right)=g^{″}\left(c_t^4\right)=g^{″}\left(c_t^5\right)=0$, and $g^{″}\left(u\right)=g^{\prime }\left(u\right)$ otherwise. It is clear that $g^{″}$ is a Roman domination function on $GIR$ graph $G^{\prime }$ and $w\left(g^{″}\right)<w\left(g^{\prime }\right)$. There is a contradiction with our assumption that the weight of $g^{\prime }$ is minimum. The conclusion is proved.   □

Claim 5.

Let $H_i$ be the subgraph of $G^{\prime }$ induced by the vertex set $(A_i\cup B_i)$, then $g^{\prime }\left(H_i\right)\ge 3$ for each $i⩽n$.

Proof. 

Without loss of generality, we assume that $g^{\prime }\left(H_i\right)\le 2$. There is no vertex that connects all the other vertices on $H_i$, so $g^{\prime }\left(H_i\right)\le 2$ does not make all the vertices on $H_i$ under dominated, this is a contradiction. Therefore, $g^{\prime }\left(H_i\right)\ge 3$ for each $i⩽n$.   □

Now, we proceed to prove Lemma 4. Firstly, we define a function $g:V\left(G\right)\to \{0,1,2\}$ satisfying that for each $i⩽n$, if $g^{\prime }\left(a_i^1\right)=2$ and $g^{\prime }\left(v_i\right)=0$, let $g\left(v_i\right)=1$; $g\left(v_i\right)=g^{\prime }\left(v_i\right)$ otherwise.

Since function $g^{\prime }$ is a Roman domination function on $GIR$ graph $G^{\prime }$, it implies that g is a Roman domination function on graph G. By Claims 4 and 5, we have $w\left(g\right)\le w\left(g^{\prime }\right)-5n$. By the known condition $w\left(g^{\prime }\right)\le k+5n$, we come to conclusion $w\left(g\right)\le k$. The conclusion of Lemma 4 is proved.

For general graphs, the decision problem of RDF is $NP$-complete, by Lemma 4, we know that for $GIR$ graphs the decision problem of RDF is $NP$-complete.

By Lemmas 3 and 4, we came to the final conclusion.

Theorem 2.

In $GIR$ graphs, the independent Roman domination problem is solvable in polynomial time and the Roman domination problem is $NP$-complete.

Below, we introduce another special graph, the $GR$ graph.

Construction 3.

Let graph G have n vertices. For any vertex $v_i$ in graph G, we define some corresponding vertex sets and edge sets.

• $A_i=\{a_i^j:j\in \left[7\right]\}$.
• $B_i=\{b_i^j:j\in [7n+1]\}$.
• $E_i^A=\{a_i^1{a}_i^2,a_i^2{a}_i^3,a_i^3{a}_i^4,a_i^4{a}_i^5,a_i^5{a}_i^6,a_i^6{a}_i^1,a_i^2{a}_i^4,a_i^1{a}_i^7,a_i^3{a}_i^7,a_i^6{a}_i^7\}$.

(a) 

For any vertex $v_i$ in the graph G, add the set of vertices $\left\{s_i\right\}\bigcup A_i\bigcup B_i$.

(b) 

For any vertex $v_i$ in the graph G, add the set of edges $\left\{v_i{a}_i^1\right\}\bigcup E_i^A\bigcup \left\{a_i^1{s}_i\right\}\bigcup \{s_i{b}_i^j:j\in [7n+1]\}$.

On the basis of graph G, the new graph formed according to the above construction methods is called $GR$ graph. See Figure 4.

Lemma 5.

Let $G^{\prime }=(V^{\prime },E^{\prime })$ be a $GR$ graph which is constructed from graph $G=(V,E)$, we have ${\gamma }_R\left(G^{\prime }\right)=6n$.

Proof. 

Now, we define a function $f:V^{\prime }\to \{0,1,2\}$ satisfying that for each $i⩽n$,

• $f\left(a_i^1\right)=f\left(a_i^4\right)=2$, $f\left(p\right)=0$$p\in A_i\setminus \{a_i^1,a_i^4\}$.
• $f\left(s_i\right)=2$.
• $f\left(p\right)=0$ otherwise.

It is clear that function f is a Roman domination function on $GR$ graph $G^{\prime }$, and the weight of f is $6n$. So we have ${\gamma }_R\left(G^{\prime }\right)\le 6n$.   □

Claim 6.

Let $G^{\prime }=(V^{\prime },E^{\prime })$ be a $GR$ graph which is constructed from graph $G=(V,E)$. We have ${\gamma }_R\left(G^{\prime }\right)\ge 6n$.

Proof. 

Let $H_i$ be the subgraph of $GR$ graph $G^{\prime }$ which is induced by the vertex set $(\left\{s_i\right\}\bigcup A_i\bigcup B_i)$ for each $i⩽n$. We assume that there exists a Roman domination function $f^{\prime }$ on graph $G^{\prime }$ and $w\left(f^{\prime }\right)<6n$. It can infer that there exists a t satisfying $w\left(f^{\prime }\right)<6$ for subgraph $H_t$. It is obvious that ${\sum }_{v\in A_t}{f}^{\prime }\left(v\right)\ge 4$ and ${\sum }_{v\in \left\{s_t\right\}\bigcup B_t}{f}^{\prime }\left(v\right)\ge 2$; otherwise it contradicts that $f^{\prime }$ is a Roman domination function. So we can infer that ${\sum }_{v\in V\left(H_t\right)}{f}^{\prime }\left(v\right)\ge {\sum }_{v\in A_t}{f}^{\prime }\left(v\right)+{\sum }_{v\in \left\{s_t\right\}\bigcup B_t}{f}^{\prime }\left(v\right)\ge 4+2=6$.

This contradicts the assumption ${\sum }_{v\in V\left(H_t\right)}{f}^{\prime }\left(v\right)<6$. So we have $w\left(f^{\prime }\right)\ge 6n$ Therefore, Claim 6 is proved.

By Claim 6, we have ${\gamma }_R\left(G^{\prime }\right)\ge 6n$. This implies that ${\gamma }_R\left(G^{\prime }\right)=6n$. Therefore, the Lemma 5 is proved.   □

Lemma 6.

Let $G^{\prime }=(V^{\prime },E^{\prime })$ be a $GR$ graph which is constructed from graph $G=(V,E)$. Then, graph G has an independent Roman domination function where the weight at most k if and only if $GR$ graph $G^{\prime }$ has an independent Roman domination function where the weight at most $k+6n$.

Proof. 

Let $H_i$ be the subgraph of $GR$ graph $G^{\prime }$ which is induced by the vertex set $(\left\{s_i\right\}\bigcup A_i\bigcup B_i)$ for each $i⩽n$.

(Necessity:) We assume that graph G has an independent Roman domination function g and $w\left(g\right)⩽k$. Next, we define a function $g^{\prime }:V^{\prime }\left(G^{\prime }\right)\to \{0,1,2\}$ that satisfies the following conditions:

• (1): if $g\left(v_i\right)=0$, let $g^{\prime }\left(v_i\right)=0,g^{\prime }\left(a_i^1\right)=g^{\prime }\left(a_i^4\right)=g^{\prime }\left(s_i\right)=2$, and $g^{\prime }\left(p\right)=0$ for $p\in V\left(H_i\right)\setminus \{a_i^1,a_i^4,s_i\}$.
• (2): if $g\left(v_i\right)=1$, let $g^{\prime }\left(v_i\right)=1,g^{\prime }\left(a_i^4\right)=g^{\prime }\left(a_i^7\right)=g^{\prime }\left(s_i\right)=2$, and $g^{\prime }\left(p\right)=0$ for $p\in V\left(H_i\right)\setminus \{a_i^4,a_i^7,s_i\}$.
• (3): if $g\left(v_i\right)=2$, let $g^{\prime }\left(v_i\right)=2,g^{\prime }\left(a_i^4\right)=g^{\prime }\left(a_i^7\right)=g^{\prime }\left(s_i\right)=2$, and $g^{\prime }\left(p\right)=0$ for $p\in V\left(H_i\right)\setminus \{a_i^4,a_i^7,s_i\}$.

It is obvious that $g^{\prime }$ is an independent Roman domination function on $GR$ graph $G^{\prime }$. Since we know that $w\left(g\right)\le k$, by (1)–(3), we have $w\left(g^{\prime }\right)\le k+6n$. Therefore, function $g^{\prime }$ is an independent Roman domination function on $GR$ graph $G^{\prime }$ and $w\left(g^{\prime }\right)\le k+6n$. We have completed the proof of the necessity.

(Sufficiency:) We assume that $G^{\prime }$ has an independent Roman domination function and the weight at most $k+6n$. Now, we define a function $f^{\prime }:V^{\prime }\left(G^{\prime }\right)\to \{0,1,2\}$ is an independent Roman domination function which has the minimum weight. It is clear that $w\left(f^{\prime }\right)\le k+6n$.    □

Lemma 7

([27]). For any graph G of order n, $i_R\left(G\right)\le n$.

Claim 7.

$w\left(f^{\prime }\right)\le 7n$

Proof. 

Through the proof of necessity, we know that given an independent Roman domination function which the weight at most k on graph G, we can find an independent Roman domination function on $GR$ graph $G^{\prime }$ which the weight at most $k+6n$. By Lemma 7, we know that for any graph G of order n, $i_R\left(G\right)\le n$. Therefore, we can get an independent Roman domination function on $G^{\prime }$ which the weight at most $7n$. We have the fact that $f^{\prime }$ is the independent Roman domination function with the minimum weight, so $w\left(f^{\prime }\right)\le 7n$.    □

Claim 8.

$f^{\prime }\left(s_i\right)=2$ for each $i⩽n$.

Proof. 

Conversely, we assume that there exists a t satisfying that $f^{\prime }\left(s_t\right)\ne 2$.

If $f^{\prime }\left(s_t\right)=1$, for each $b_t^j\in B_t$, $f^{\prime }(b_t^j)=0$, it is easy to prove that there is a contradiction with $f^{\prime }$ is an IRDF.

If $f^{\prime }\left(s_t\right)=0$, this implies that $f^{\prime }(b_t^j)>0$ for each $b_t^j\in B_t$. Since $\mid B_t\mid =7n+1$, we can infer that $w\left(f^{\prime }\right)>7n$. It contradicts the conclusion of Claim 7. Hence, the conclusion is proven.    □

Claim 9.

$f^{\prime }\left(a_i^1\right)=0$ for each $i⩽n$.

Proof. 

Conversely, we assume that there exists a t satisfying that $f^{\prime }\left(a_t^1\right)>0$. We can know that the neighbor of $a_t^1$ must be assigned 0 for which $f^{\prime }\left(s_t\right)=0$. This is a contradiction by Claim 8. Hence, the conclusion is proven.    □

Claim 10.

${\sum }_{v\in V\left(H_i\right)}{f}^{\prime }\left(v\right)\ge 6$ for each $i⩽n$.

Proof. 

It can be verified that ${\sum }_{v\in A_i}{f}^{\prime }\left(v\right)\ge 4$ for each $i⩽n$; otherwise it would contradict the known fact that $f^{\prime }$ is an independent Roman domination function on $GR$ graph $G^{\prime }$. Futher, by Claim 8, we know that $f^{\prime }\left(s_i\right)=2$. Therefore, we have

${\sum }_{v\in V\left(H_i\right)}{f}^{\prime }\left(v\right)\ge {\sum }_{v\in A_i}{f}^{\prime }\left(v\right)+f^{\prime }\left(s_i\right)\ge 4+2=6$.

We now return to prove the sufficiency part of Lemma 6. Define $f:V\left(G\right)\to \{0,1,2\}$ as $f\left(v_i\right)=f^{\prime }\left(v_i\right)$ for each $i⩽n$. We want to show that f is an independent Roman domination function on graph G. We know that $N_{G^{\prime }}\left(v_t\right)=N_G\left(v_t\right)\cup \left\{a_t^1\right\}$. From Claim 9, we have that $f^{\prime }\left(a_t^1\right)=0$. Hence, $v_t$ does not dominated by $a_t^1$. So we can infer that f is an independent Roman domination function on graph G. According to the known condition $w\left(f^{\prime }\right)\le k+6n$ and Claim 10, we deduce that $w\left(f\right)\le w\left(f^{\prime }\right)-6n\le k$.

For general graphs, the decision problem of IRDF is $NP$-complete [2], by Lemma 6, we know that for $GR$ graphs the decision problem of IRDF is $NP$-complete.

By Lemmas 5 and 6, we have reached the final conclusion.    □

Theorem 3.

In $GR$ graphs, the Roman domination problem is solvable in polynomial time and the independent Roman domination problem is $NP$-complete.

4. A Linear Algorithm for Independent Roman Domination in Trees

In this section, we propose a linear-time algorithm for computing the independent Roman dominating number $i_R\left(G\right)$ in trees. Let ${\gamma }_{IRD}\left(G\right)$ similarly represent the independent Roman domination number of graph G.

Let u be a special vertex of graph G, and an independent Roman domination function with minimum weight on graph G satisfy that $f\left(u\right)\in \{0,1,2\}$. So it is useful to consider the following three domination problems.

${\gamma }_{IRD}^0(G,u)=min\{\omega \left(f\right):$ f is an IRDF of G and $f\left(u\right)=0\}$

${\gamma }_{IRD}^1(G,u)=min\{\omega \left(f\right):$ f is an IRDF of G and $f\left(u\right)=1\}$

${\gamma }_{IRD}^2(G,u)=min\{\omega \left(f\right):$ f is an IRDF of G and $f\left(u\right)=2\}$

Lemma 8.

For any graph G with a specific vertex u, we have

${\gamma }_{IRD}(G,u)=min\{{\gamma }_{IRD}^0(G,u),{\gamma }_{IRD}^1(G,u),{\gamma }_{IRD}^2(G,u)\}$

${\gamma }_{IRD}^{00}(G,u)=min\{\omega \left(f\right):f$ is an IRDF of $G-u\}$.

Note that ${\gamma }_{IRD}^{00}(G,u)\le {\gamma }_{IRD}^0(G,u),$ since an IRDF f of G and $f\left(u\right)=0$ is also an IRDF of $G-u.$

Theorem 4.

Suppose that graph G contains special vertices u and graph H contains special vertices v, and graph I is obtained by adding a new $uv$ edge to the disjoint union of graph G and H. Therefore, the following equations are true.

(1) 

${\gamma }_{IRD}^0(I,u)=min\{{\gamma }_{IRD}^0(G,u)+{\gamma }_{IRD}^0(H,v),{\gamma }_{IRD}^0(G,u)+{\gamma }_{IRD}^1(H,v),{\gamma }_{IRD}^{00}(G,u)+{\gamma }_{IRD}^2(H,v)\}$

(2) 

${\gamma }_{IRD}^1(I,u)={\gamma }_{IRD}^1(G,u)+{\gamma }_{IRD}^0(H,v)$

(3) 

${\gamma }_{IRD}^2(I,u)={\gamma }_{IRD}^2(G,u)+{\gamma }_{IRD}^{00}(H,v)$

(4) 

${\gamma }_{IRD}^{00}(I,u)={\gamma }_{IRD}^{00}(G,u)+{\gamma }_{IRD}(H,v)$

= ${\gamma }_{IRD}^{00}(G,u)+min\{{\gamma }_{IRD}^0(H,v),{\gamma }_{IRD}^1(H,v),{\gamma }_{IRD}^2(H,v)\}$

Proof. (1) We can conclude from the fact that f is an IRDF of I with $f\left(u\right)=0$ if and only if $f=g\bigcup h,$ where g is an IRDF of G with $g\left(u\right)=0$ and h is an IRDF of H with $h\left(v\right)=0$, g is an IRDF of G with $g\left(u\right)=0$ and h is an IRDF of H with $h\left(v\right)=1$, or g is an IRDF of $G-u$ and h is an IRDF of H with $h\left(v\right)=2$.

(2) We can conclude from the fact that f is an IRDF of I with $f\left(u\right)=1$ if and only if $f=g\bigcup h,$ where g is an IRDF of G with $g\left(u\right)=1$ and h is an IRDF of H with $h\left(v\right)=0$.

(3) We can conclude from the fact that f is an IRDF of I with $f\left(u\right)=2$ if and only if $f=g\bigcup h,$ where g is an IRDF of G with $g\left(u\right)=2$ and h is an IRDF of $H-v$.

(4) We can conclude from the fact that f is an IRDF of $I-u$ if and only if $f=g\bigcup h,$ where g is an IRDF of $G-u$ and h is an IRDF of H.    □

Lemma 8 and Theorem 4 give the following dynamic programming algorithm for the independent Roman domination problem in trees (See Algorithm 1). The tree ordering in the algorithm refers to any traversal order of the tree, and pre-order, in-order, and post-order traversal are possible.

Algorithm 1 Independent Roman Domination

Input: A tree T with a tree ordering $\{v_1,v_2,...,v_n\}$. Output: the Independent Roman domination number ${\gamma }_{IRD}\left(T\right)$ of T. 1: for$i=1$ to n do 2:     ${\gamma }^{00}\left(v_i\right)$ = 0 3:     ${\gamma }^0\left(v_i\right)=\infty$ 4:     ${\gamma }^1\left(v_i\right)=1$ 5:     ${\gamma }^2\left(v_i\right)=2$ 6: for$i=1$ to $n-1$ do 7:     let $v_j$ be the parent of $v_i$ 8:     ${\gamma }^0\left(v_j\right)=min\{{\gamma }^0\left(v_j\right)+{\gamma }^0\left(v_i\right),{\gamma }^0\left(v_j\right)+{\gamma }^1\left(v_i\right),{\gamma }^{00}\left(v_j\right)+{\gamma }^2\left(v_i\right)\}$ 9:     ${\gamma }^1\left(v_j\right)={\gamma }^1\left(v_j\right)+{\gamma }^0\left(v_i\right)$ 10:     ${\gamma }^2\left(v_j\right)={\gamma }^2\left(v_j\right)+{\gamma }^{00}\left(v_i\right)$ 11:     ${\gamma }^{00}\left(v_j\right)={\gamma }^{00}\left(v_j\right)+min\{{\gamma }^0\left(v_i\right),{\gamma }^1\left(v_i\right),{\gamma }^2\left(v_i\right)\}$ 12: return min $\{{\gamma }^0\left(v_n\right),{\gamma }^1\left(v_n\right),{\gamma }^2\left(v_n\right)\}$

Below, we take Figure 5 as an example to show the changes in the values of intermediate parameters during the execution of each step of the algorithm in the form of a table (See

Table 1. Initial state.

	${\mathit{v}}_1$	${\mathit{v}}_2$	${\mathit{v}}_3$	${\mathit{v}}_4$	${\mathit{v}}_5$	${\mathit{v}}_6$
${\gamma }^0$	∞	∞	∞	∞	∞	∞
${\gamma }^1$	1	1	1	1	1	1
${\gamma }^2$	2	2	2	2	2	2
${\gamma }^{00}$	0	0	0	0	0	0

,

Table 2. i = 1.

	${\mathit{v}}_1$	${\mathit{v}}_2$	${\mathit{v}}_3$	${\mathit{v}}_4$	${\mathit{v}}_5$	${\mathit{v}}_6$
${\gamma }^0$	∞	∞	∞	2	∞	∞
${\gamma }^1$	1	1	1	∞	1	1
${\gamma }^2$	2	2	2	2	2	2
${\gamma }^{00}$	0	0	0	1	0	0

,

Table 3. i = 2.

	${\mathit{v}}_1$	${\mathit{v}}_2$	${\mathit{v}}_3$	${\mathit{v}}_4$	${\mathit{v}}_5$	${\mathit{v}}_6$
${\gamma }^0$	∞	∞	∞	3	∞	∞
${\gamma }^1$	1	1	1	∞	1	1
${\gamma }^2$	2	2	2	2	2	2
${\gamma }^{00}$	0	0	0	2	0	0

,

Table 4. i = 3.

	${\mathit{v}}_1$	${\mathit{v}}_2$	${\mathit{v}}_3$	${\mathit{v}}_4$	${\mathit{v}}_5$	${\mathit{v}}_6$
${\gamma }^0$	∞	∞	∞	4	∞	∞
${\gamma }^1$	1	1	1	∞	1	1
${\gamma }^2$	2	2	2	2	2	2
${\gamma }^{00}$	0	0	0	3	0	0

,

Table 5. i = 4.

	${\mathit{v}}_1$	${\mathit{v}}_2$	${\mathit{v}}_3$	${\mathit{v}}_4$	${\mathit{v}}_5$	${\mathit{v}}_6$
${\gamma }^0$	∞	∞	∞	4	∞	2
${\gamma }^1$	1	1	1	∞	1	5
${\gamma }^2$	2	2	2	2	2	5
${\gamma }^{00}$	0	0	0	3	0	2

and

Table 6. i = 5.

	${\mathit{v}}_1$	${\mathit{v}}_2$	${\mathit{v}}_3$	${\mathit{v}}_4$	${\mathit{v}}_5$	${\mathit{v}}_6$
${\gamma }^0$	∞	∞	∞	4	∞	3
${\gamma }^1$	1	1	1	∞	1	∞
${\gamma }^2$	2	2	2	2	2	5
${\gamma }^{00}$	0	0	0	3	0	3

). We take the result of the post-order traversal as the tree order.

It can be seen from Table 6, $min\{{\gamma }^0\left(v_6\right),{\gamma }^1\left(v_6\right),{\gamma }^2\left(v_6\right)\}=3$. Therefore, the independent Roman domination number of this tree is 3.

5. Conclusions

In this paper, we research the decision problem IRDF corresponding to independent Roman dominating functions is $NP$-complete, even when restricted to chordal bipartite graphs. We prove the complexity difference between DECIDE-RDF and DECIDE-IRDF. At the same time, we also propose a linear-time algorithm for computing the independent Roman domination number in trees. We believe that linear-time algorithms on block graphs and interval graphs are also possible, and we will continue to study this aspect in the future.