Complexity of signed total $k$-Roman domination problem in graphs

1.   Introduction

In this paper, $G$ is a simple graph with finite vertex set $V = V(G)$ and edge set $E = E(G)$. Assume $s \in V(G)$ and $S = \{-1, 1, 2\}$, we will use the following notations.

If there is a function $f$ meeting the following conditions: (i) each vertex $y$ with $f(y) = -1$ has at least one neighbor $t$ with $f(t) = 2$, (ii) $\sum _{t\in N(y)} f(t)\geq k$ for any vertex $y \in V$, and then $f$ is called a signed total Roman $k$-dominating function (STRkDF). Let $\mathfrak{F}(G)$ denote the set of all the STRkDFs of $G$. The weight of an STRkDF $f$, denoted by $\omega(f)$, is defined to be the value $\sum_{y\in V(G)}f(y)$. The signed total Roman $k$-domination number of $G$, denoted $\gamma_{stR}^k(G)$, is weight of an STRkDF $f$ where $\omega(f) = \min\{\omega(g) \mid g \in \mathfrak{F}(G)\}$. An STRkDF of weight $\gamma_{stR}^k(G)$ is called a $\gamma_{stR}^k(G)$-function. The signed total Roman $k$-domination number must exist if $\delta(G)\geq \frac{k}{2}$. For an STRkDF $f$, let $V_{r} = \{t\in V(G)\colon f(t) = r\}$ for $r\in S$. Because this partition determines $f$, we then write $f = (V_{-1}, V_{1}, V_{2})$ equivalently. The signed total Roman domination number and signed total $k$-domination number was introduced and investigated in ^[12,14]. This parameter is introduced and investigated in a more general setting ^[9,11]. There are several works that considered the decision problems for the signed Roman domination parameters (see ^[1,2,3,13]). For more details on Roman domination and its variants, we refer the reader to the recent book chapters and surveys ^[4,5,6,7,8].

In this article, we will show that the decision problems for the signed total Roman $k$-domination numbers for $k\in\{1, 2\}$ are NP-hard. In other words, there are no polynomial algorithms to compute this parameter unless P = NP.

2.   Complexity result

In this section we will give the NP-complete result for the signed total Roman $k$-domination problem on bipartite and chordal graphs for $k\in\{1, 2\}$.

Signed total Roman k-domination problem(STRkDP) for ${\bf k\in\{1, 2\}}$:

Instance: A graph $G$ and a positive integer $\ell\leq|V(G)|$.

Question: Does $G$ have an STRkDF with weight at most $\ell$?

We will prove that STRkDP is NP-complete by reducing the especial case of Exact Cover by 3-sets (X3C) to which we refer as X3C3. The NP-completeness of X3C3 was proven in 2008 by Hickey et al. ^[10].

X3C3

Instance: A set of elements $X$ and a collection $\mathscr{C}$ of $m$ 3-element subsets of $X$ where $\mid X\mid = m = 3q$, with the condition that every element appears in exactly 3 members of $\mathscr{C}$.

Question: Does there exist a subcollection $\mathscr{C}'\subset \mathscr{C}$ with the condition that each element of $X$ appears in exactly one member of $\mathscr{C}'$?

Now we show that the problem above is NP-hard, even when restricted to the case $k = 1$ and to bipartite and chordal graphs.

Theorem 1. Problem STR1DP is NP-Complete for bipartite and chordal graphs.

Proof. Clearly STR1DP is a member of $\mathrm{NP}$ since we can verify that a function $f:V(G)\to S$ has weight at most $\ell$ and determine whether $f \in \mathfrak{F}(G)$ in polynomial time. Now let us transform any instance of X3C3 into an instance $G$ of STR1DP satisfying that STR1DP has a solution if and only if X3C3 has a solution. Let $X = \{x_{1}, x_{2}, \ldots, x_{3q}\}$ and $\mathscr{C} = \{C_{1}, C_{2}, \ldots, C_{3q}\}$ be an arbitrary instance of X3C3.

First we construct the bipartite graph $G_1.$ For each $x_{i}\in X,$ we create a single vertex $x_{i}$ to which we associate a copy of the graph $H_{i}$, obtained from a cycle $u_ip_iv_iy_iu_i$ by adding two pendant edges at each of vertices $u_i, p_i, v_i$, as shown in Figure 1 by adding the edge $y_{i}x_{i}.$ For each $C_{j},$ we create a vertex $c_{j}$ to which we associate a copy of the graph $H_{j}^{\prime }$ as shown in Figure 1 by adding the edges $c_{j}z_{j}$ and $c_{j}w_{j}.$ Now to obtain the graph $G_1$, we add edges $c_{j}x_{i}$ if $x_{i}\in C_{j}$. Since $G_1$ has no cycle of odd length, $G_1$ is a bipartite graph (see Figure 2). Now let $A = \{c_{1}, c_{2}, \ldots, c_{3q}\}$ and set $\ell = q.$

Figure 1.  The graphs $H_i$ and $H^{\prime}_j$.

DownLoad: Full-Size Img PowerPoint

Figure 2.  NP-completeness of STR1D for chordal graphs , here $q = 2$ and $\gamma_{stR}^1(G_1) = 2$.

DownLoad: Full-Size Img PowerPoint

Figure 3.  The graphs $F_i$ and $F'_j$.

DownLoad: Full-Size Img PowerPoint

Figure 4.  NP-completeness of STR2D for chordal graphs , here $q = 2$ and $\gamma_{stR}^1(G_2) = 2$.

DownLoad: Full-Size Img PowerPoint

To prove that this is indeed a transformation, we only need to show that $\gamma_{stR}^1(G_1)\leq\ell$ if, and only if, there is a truth assignment for $X$ that satisfies all clauses in $\mathscr{C}$. This aim can be obtained the following:

Suppose that $\mathscr{C}^{\prime }$ is a solution of X3C3. Define the signed total 1- Roman dominating function $f$ on $G_1$ of weight $\ell$ as follows: for every $i\in \{1, ..., 3q\}$, let $f(u_{i}) = f(v_{i}) = f(p_{i}) = f(z_{i}) = f(w_{i}) = f(t_{i}) = 2$ and $f(y_{i}) = 1;$ for every $C_{j}\in \mathscr{C}^{\prime }$, let $f(c_{j}) = 2$ and for every $C_{j}\notin \mathscr{C}^{\prime }$ let $f(c_{j}) = 1;$ and let $f(x_i) = -1$. Note that since $\mathscr{C}^{\prime }$ exists, $\left\vert \mathscr{C}^{\prime }\right\vert = q$, and so the number of $c_{j}$ 's with weight 2 is $q$, having disjoint neighborhoods in $\{x_{1}, x_{2}, \ldots, x_{3q}\}$. Now it is straightforward to see that $f$ is a signed total Roman 1- dominating function with weight $\omega(f) = q = \ell$.

Conversely, assume there exists a function $h \in \mathfrak{F}(G_1)$ with $\omega(h) \leq \ell$. Among all these functions, let $f = (V_{-1}, V_{1}, V_{2})$ be one such function that assigns smallest possible values to the leaves of $G_1$. Clearly $f$ assigns a positive value to each support vertex. We claim that $f(x) = -1$ for any leaf $x$ of $G_1$. Suppose, to the contrary, that $f(x)\ge 1$ for some leaf of $G_1$. Without loss of generality that we may assume that $x\in V(H_1)\cup V(H_1')$. First let $x\in V(H_1)$. If $f(p_1^1)\ge 1$ and $f(p_1^2)\ge 1$, then the function $g$ defined by $g(p_1) = 2, g(p_1^1) = -1$, $g(p_1^2) = 1$ and $g(u) = f(u)$ otherwise, is a STR1DF of $G_1$ of weight less than $\omega(f)$ which is a contradiction. Thus we may assume that $f(p_1^1) = -1$. It follows that $f(p_1) = 2$. Likewise, we may assume that $f(u_1^1) = f(v_1^1) = -1$ implying that $f(u_1) = f(v_1) = 2$. Since $f$ has minimum weight, we deduce that $f(p_1^2) = -1$. Hence $x\in \{u_1^2, v_1^2\}$. If $f(y_1)\ge 1$, then similarly we have $f(u_1^2) = -1$ and $f(v_1^2) = -1$ which leads to a contradiction. Hence $f(y_1) = -1$. Now the function $g$ defined by $g(x) = -1$, $g(y_1) = 1$ and $g(u) = f(u)$ otherwise, is a STR1DF of $G_1$ of weight $\omega(f)$ contradicting the choice of $f$. Now let $x\in V(H_1)$. If $f(t_1^i)\ge 1$ and $f(t_1^k)\ge 1$ for some $i\neq k$, then the function $g$ defined by $g(t_1^i) = -1, g(t_1) = 2$ and $g(u) = f(u)$ otherwise, is a STR1DF of $G_1$ of weight less than $\omega(f)$ which is a contradiction. Thus we may assume without loss of generality that $f(t_1^1) = f(t_1^2) = -1$. It follows that $f(t_1) = 2$. Then we have $f(t_1)+f(c_1)\ge 1$. If $f(z_1^1)\ge 1$ and $f(z_1^2)\ge 1$, then the function $g$ defined by $g(z_1^1) = -1, g(z_1) = 2$ and $g(u) = f(u)$ otherwise, is a STR1DF of $G_1$ of weight less than $\omega(f)$ which is a contradiction again. Hence we assume that $f(z_1^1) = -1$. Likewise, we may assume that $f(w_1^1) = -1$. Since $f$ is a STR1DF of $G_1$, we must have $f(z_1) = f(w_1) = 2$. Since $f$ has minimum weight, we deduce that $f(t_1^3) = -1$. Thus $x\in \{z_1^2, w_1^2\}$. If $f(c_1)\ge 1$, then the function $g$ defined by $g(z_1^2) = g(w_1^2) = -1$ and $g(u) = f(u)$, otherwise is a STR1DF of $G_1$ of weight less than $\omega(f)$ which is a contradiction again. Hence $f(c_1) = -1$. Now the function $g$ defined by $g(x) = -1$, $g(c_1) = 1$ and $g(u) = f(u)$ otherwise, is a STR1DF of $G_1$ of weight $\omega(f)$ contradicting the choice of $f$. This proves the claim. Thus $f(y) = 2$ for every support vertex $y$ of $G_1$. Since $\sum_{u\in N(z_{i})-\{c_{j}\}}f(u) = \sum_{u\in N(w_{i})-\{c_{j}\}}f(u) = 0$, we must have $f(c_{j})\geq 1$ for every $j$. Also, we observe that $\sum_{u\in N(u_{i})-\{y_{i}\}}f(u) = 0$ and $\sum_{u\in N(v_{i})-\{y_{i}\}}f(u) = 0$, and thus we must have $f(y_{i})\geq 1$ for every $i$. It follows clearly that no $x_{i}$ needs to be assigned a positive value under $f,$ and thus $x_{i}\in V_{-1}$ for every $i$. If $y_{i}\in V_{2}$ for some $i,$ then we can reassign $y_{i}$ and any $c_{r}$ adjacent to $x_{i}$ the values $1$ and $2,$ respectively. So we may assume that $y_{i}\in V_{1}$ for every $i.$ Now, since $f$ has weight at most $\ell = q$, and every $x_{i}$ needs to be adjacent to a vertex assigned a $2,$ there must exist $q$ vertices of $A$ assigned a $2$ under $f$ and the remaining vertices of $A$ belongs to $V_{1}.$ On the other hand, since each $c_{j}$ has exactly three neighbors in $X$, we conclude that $\mathscr{C}^{\prime } = \{C_{j}:f(c_{j}) = 2\}$ is an exact cover for $\mathscr{C}$.

Now we construct the chordal graph $G_2.$ For each $x_i\in X$, we create a single vertex $x_i$ to which we associate a copy of the graph $F_i$, obtained from a cycle $u_ip_iv_iy_iu_i$ by adding the edge $u_iv_i$, adding one pendant edge at $p_i$ and three pendant edges at $u_i$ and $v_i$, as shown in Figure 2 by adding the edge $y_ix_i$. For each $C_j$ we create a vertex $c_j$ to which we associate a copy of the graph $F'_j$ as shown in Figure 2, by adding the edges $c_jz_j$ and $c_jw_j$. Now to obtain the graph $G_2$, we add edges $c_jx_i$ if $x_i\in C_j$ and all edges between vertices $c_j'$s. Clearly, any cycle in $G_2$ with length at least four has a chord and hence $G_2$ is a chordal graph (see Figure 4). Let $A = \{c_1, c_2, \ldots, c_{3q}\}$ and set $\ell = q$.

To prove that this is indeed a transformation, we only need to show that $\gamma_{stR}^1(G_2)\leq\ell$ if, and only if, there is a truth assignment for $X$ that satisfies all clauses in $\mathscr{C}$. This aim can be obtained the following: Suppose that $\mathscr{C}'$ is a solution of $X3C3$. Define a signed total 1-Roman dominating function $g$ on $G_2$ of weight $\ell$ as follows: for every $i\in\{1, 2, \ldots, 3q\}, g(u_i) = g(v_i) = g(z_i) = g(w_i) = g(p_i) = 2, g(y_i) = 1$; if $C_j\in \mathscr{C}'$, then let $g(c_j) = 2$ and if $C_j\notin \mathscr{C}'$, then let $g(c_j) = 1$; and let $g(x_i) = -1$. Note that since $\mathscr{C}^{\prime }$ exists, $\left\vert \mathscr{C}^{\prime }\right\vert = q$, and so the number of $c_{j}$ 's with weight 2 is $q$, having disjoint neighborhoods in $\{x_{1}, x_{2}, \ldots, x_{3q}\}$. Now it is straightforward to see that $g$ is a signed total Roman 1- dominating function with weight $\omega(g) = q = \ell$.

Conversely, assume there exists a function $h \in \mathfrak{F}(G_2)$ with $\omega(h) \leq \ell$. Among all these functions, let $g = (V_{-1}, V_{1}, V_{2})$ be one such function that assigns smallest possible values to the leaves of $G_2$. As in the proof for bipartite graph, we can show that $g(x) = -1$ for any leaf $x$ of $G_2$, and thus $g(y) = 2$ for every support vertex $y$ of $G_2$. Since $\sum_{u\in N(z_{i})-\{c_{j}\}}g(u) = \sum_{u\in N(w_{i})-\{c_{j}\}}g(u) = 0$, we must have $g(c_{j})\geq 1$ for every $j$. Also, for $G_2$ we observe that $\sum_{u\in N(u_{i})-\{y_{i}\}}g(u) = 1$ and$\sum_{u\in N(v_{i})-\{y_{i}\}}g(u) = 1$, and thus we must have $g(y_{i})\geq 1$ for every $i$. It follows clearly that no $x_{i}$ needs to be assigned a positive value under $g$ and thus $x_{i}\in V_{-1}$ for every $i$. If $y_{i}\in V_{2}$ for some $i,$ then we can reassign $y_{i}$ and any $c_{r}$ adjacent to $x_{i}$ the values $1$ and $2,$ respectively. So we may assume that $y_{i}\in V_{1}$ for every $i.$ Now, since $g$ has weight at most $\ell = q$, and every $x_{i}$ needs to be adjacent to a vertex assigned a $2,$ there must exist $q$ vertices of $A$ assigned a $2$ under $g$ and the remaining vertices of $A$ belongs to $V_{1}.$ On the other hand, since each $c_{j}$ has exactly three neighbors in $X$, we conclude that $\mathscr{C}^{\prime } = \{C_{j}:g(c_{j}) = 2\}$ is an exact cover for $\mathscr{C}$.

The case $k = 2$

Theorem 2. Problem STR2DP is NP-Complete for bipartite and chordal graphs.

Proof. Similar as the proof of the Theorem 1, clearly STR2DP is a member of $\mathrm{NP}$ since we can verify that a function $f:V(G)\longrightarrow S$ has weight at most $\ell$ and determine whether $f \in \mathfrak{F}(G)$ in polynomial time. Now let us transform any instance of X3C3 into an instance $G$ of STR2DP satisfying that STR2DP has a solution if and only if X3C3 has a solution. Let $X = \{x_{1}, x_{2}, \ldots, x_{3q}\}$ and $\mathscr{C} = \{C_{1}, C_{2}, \ldots, C_{3q}\}$ be an arbitrary instance of X3C3. We now construct the bipartite graph $G_{3}$ and the chordal graph $G_{4}$, respectively.

For each $x_{i}\in X,$ we create a single vertex $x_{i}$ to which we associate a copy of the graph $E_{i}$ as shown in Figure 5 by adding the edge $y_{i}x_{i}.$ For each $C_{j},$ we create a vertex $c_{j}$ to which we associate a copy of the graph $E_{j}^{\prime }$ as shown in Figure 5 by adding the edges $c_{j}u_{j}$ and $c_{j}v_{j}.$ Now to obtain the graph $G_3$, we add edges $c_{j}x_{i}$ if $x_{i}\in C_{j}$. It is clear that $G_3$ has no cycle of odd length and so $G_3$ is a bipartite graph (see Figure 6). Let $A = \{c_{1}, c_{2}, \ldots, c_{3q}\}$, and set $\ell = q.$ To prove that this is indeed a transformation, we only need to show that $\gamma_{stR}^2(G_3)\leq\ell$ if, and only if, there is a truth assignment for $X$ that satisfies all clauses in $\mathscr{C}$. This aim can be obtained the following:

Figure 5.  The graphs $E_i$ and $E^{\prime}_j$.

DownLoad: Full-Size Img PowerPoint

Figure 6.  NP-completeness of STR2D for chordal graphs , here $q = 2$ and $\gamma_{stR}^2(G_3) = 2$.

DownLoad: Full-Size Img PowerPoint

Suppose that $\mathscr{C}'$ is a solution of $X3C3$. Define a signed 2-Roman dominating function $f$ on $G_3$ of weight $\ell$ as follows: for every $i\in\{1, 2, \ldots, 3q\}$ let

Note that since $\mathscr{C}'$ exists and $|\mathscr{C}'| = q$, the number of $c_j'$s with weight $2$ is $q$, having disjoin neighborhoods in $\{x_1, x_2, \ldots, x_{3q}\}$. It is easy to see that $f$ is signed total Roman 2-dominating function with weight $\omega(f) = q$.

Conversely, first assume there exists a function $h \in \mathfrak{F}(G_3)$ with $\omega(h) \leq \ell$. {Among all these functions, let $f = (V_{-1}, V_{1}, V_{2})$ be one such function that assigns smallest possible values to the leaves of $G_3$.} As in the proof of Theorem 2.1 for bipartite graph, we can show that $f(x) = -1$ for any leaf $x$ of $G_3$, and thus $f(y) = 2$ for every support vertex $y$ of $G_3$. Since $\sum_{u\in N(u_{i})-\{c_{j}\}}f(u) = \sum_{u\in N(v_{i})-\{c_{j}\}}f(u) = 2$, we must have $f(c_{j})\geq 1$ for every $j$. Also, we observe that $\sum_{u\in N(a_{i})-\{y_{i}\}}f(u) = 1$ and thus we must have $f(y_{i})\geq 1$ for every $i$. It follows clearly that no $x_{i}$ needs to be assigned a positive value under $f,$ and thus $x_{i}\in V_{-1}$ for every $i$. If $y_{i}\in V_{2}$ for some $i,$ then we can reassign $y_{i}$ and any $c_{r}$ adjacent to $x_{i}$ the values $1$ and $2,$ respectively. So we may assume that $y_{i}\in V_{1}$ for every $i.$ Now, since $f$ has weight at most $\ell = q$, and every $x_{i}$ needs to be adjacent to a vertex assigned a $2,$ there must exist $q$ vertices of $A$ assigned a $2$ under $f$ and the remaining vertices of $A$ belongs to $V_{1}.$ Now since each $c_{j}$ has exactly three neighbors in $X$, we conclude that $\mathscr{C}' = \{C_{j}:f(c_{j}) = 2\}$ is an exact cover for $\mathscr{C}$.

Now we construct the chordal graph $G_4$.

Similar as above, for each $x_{i}\in X,$ we create a single vertex $x_{i}$ to which we associate a copy of the graph $K_{i}$ as shown in Figure 7 by adding the edge $y_{i}x_{i}.$ For each $C_{j},$ we create a vertex $c_{j}$ to which we associate a copy of the graph $K_{j}^{\prime }$ as shown in Figure 7 by adding the edges $c_{j}u_{j}$ and $c_{j}v_{j}$. Now to obtain the graph $G_4$ we add edges $c_{j}x_{i}$ if $x_{i}\in C_{j}$ and all edges between vertices $c_j'$s. Clearly, any cycle of $G_4$ with length at least four has a chord and so $G_4$ is a chordal graph (see Figure 8). Let $A = \{c_{1}, c_{2}, \ldots, c_{3q}\}$, and set $\ell = q.$ To prove that this is indeed a transformation, we only need to show that $\gamma_{stR}^2(G_4)\leq\ell$ if, and only if, there is a truth assignment for $X$ that satisfies all clauses in $\mathscr{C}$. This aim can be obtained the following:

Figure 7.  The graphs $K_i$ and $K^{\prime}_j$.

DownLoad: Full-Size Img PowerPoint

Figure 8.  NP-completeness of STR2D for chordal graphs , here $q = 2$ and $\gamma_{stR}^2(G_4) = 2$.

DownLoad: Full-Size Img PowerPoint

Suppose that $\mathscr{C}'$ is a solution of $X3C3$. Define a signed 2-Roman dominating function $g$ on $G_4$ of weight $\ell$ as follows: for every $i\in\{1, 2, \ldots, 3q\}$ let

Note that since $\mathscr{C}'$ exists and $|\mathscr{C}'| = q$, the number of $c_j'$s with weight $2$ is $q$, having disjoin neighborhoods in $\{x_1, x_2, \ldots, x_{3q}\}$. It is easy to see that $g$ is signed total Roman 2-dominating function with weight $\omega(g) = q$.

Conversely, first assume there exists a function $h \in \mathfrak{F}(G_4)$ with $\omega(h) \leq \ell$. Among all these functions, let $g = (V_{-1}, V_{1}, V_{2})$ be one such function that assigns smallest possible values to the leaves of $G_4$. As in the proof of Theorem 2.1 for bipartite graph, we can show that $g(x) = -1$ for any leaf $x$ of $G_4$, and thus $g(y) = 2$ for every support vertex $y$ of $G_4$. Since $\sum_{u\in N(u_{i})-\{c_{j}\}}g(u) = \sum_{u\in N(v_{i})-\{c_{j}\}}g(u) = 2$, we must have $g(c_{j})\geq 1$ for every $j$. Also, we observe that $\sum_{u\in N(w_{i})-\{y_{i}\}}g(u) =$ and thus we must have $g(y_{i})\geq 1$ for every $i$. It follows clearly that no $x_{i}$ needs to be assigned a positive value under $g,$ and thus $x_{i}\in V_{-1}$ for every $i$. If $y_{i}\in V_{2}$ for some $i,$ then we can reassign $y_{i}$ and any $c_{r}$ adjacent to $x_{i}$ the values $1$ and $2,$ respectively. So we may assume that $y_{i}\in V_{1}$ for every $i.$ Now, since $g$ has weight at most $\ell = q$, and every $x_{i}$ needs to be adjacent to a vertex assigned a $2,$ there must exist $q$ vertices of $A$ assigned a $2$ under $g$ and the remaining vertices of $A$ belongs to $V_{1}.$ Now since each $c_{j}$ has exactly three neighbors in $X$, we conclude that $\mathscr{C}' = \{C_{j}:g(c_{j}) = 2\}$ is an exact cover for $\mathscr{C}$.

Acknowledgments

This work was supported by the National Key R & D Program of China (Grant No. 2019YFA0706402), the Natural Science Foundation of Guangdong Province under grant 2018A0303130115 and Guangzhou Academician and Expert Workstation(No. 20200115-9).

Conflicts of interest

The authors declare that there are no known conflicts of interest associated with this paper and there has been no significant financial support for this work that could have influenced its outcome.