Positive Influence Domination in Graphs

Abstract

A subset $D\subseteq V(G)$ is said to be a positive influence dominating set of a graph G if every vertex $v\in V(G)$ has at least half of its neighbors in D. The positive influence domination number of G, denoted by $\gamma _{PI}(G)$, is the cardinality of the smallest positive influence dominating set of G. To find a smallest positive influence dominating set of G is called the positive influence domination problem. In this paper, we first establish some sharp lower bounds on $\gamma _{PI}(G)$. Next, we investigate the complexity of the positive influence domination problem and show that the decision version of it is NP-complete even when restricted to bipartite graphs and split graphs. Moreover, we prove that the positive influence domination problem on graphs with maximum degree 3 remains APX-complete.

1 Introduction

Throughout this paper, we consider only finite, simple and undirected graphs. Let $G=(V(G),E(G))$ be a graph with vertex set V(G) and edge set E(G). The open neighborhood $N_{G}(v)$ of a vertex v in G is the set of neighbors of v, where two vertices are neighbors in G if they are adjacent. Hence, $N_{G}(v) = \{u \in V(G)\mid uv \in E(G)\}$. The closed neighborhood of a vertex v is the set $N_{G}[v] = \{v\} \cup N_{G}(v)$. The degree $d_{G}(v)$ of a vertex v is the number of neighbors of v in G, that is, $d_{G}(v)=|N_{G}(v)|$. We denote by $\delta (G)$ and $\Delta (G)$ the minimum and maximum degrees of the vertices of G, respectively. A vertex v is called an odd vertex if $d_{G}(v)$ is odd. A graph G is k-regular if $d_{G}(v)= k$ for every vertex $v \in V(G)$. In particular, a 3-regular graph is also referred to as a cubic graph. Given two disjoint subsets $A,B\subseteq V(G)$, we denote the set of edges that join a vertex of A and a vertex of B in G by [A, B]. The number of edges in [A, B] is represented by e(A, B). If the graph G is clear from the context, we omit it in the above expressions.

Given a subset $S \subseteq V(G)$, the subgraph induced by S is the graph G[S] whose vertex set is S and whose edge set consists of all edges of G which have both endpoints in S. If S is a set of mutually adjacent vertices, then S is said to be a clique of G. Thus, G[S] is a complete subgraph of G. An independent set of G is a subset of vertices no two of which are adjacent, and so G[S] has no edge. A graph is a split graph if its vertex set can be partitioned into a clique and an independent set. A graph $G=(V_{1}, V_{2},\ldots ,V_{r};E)$ is said to be r-partite if its vertex set can be partitioned into r independent sets $V_{1}, V_{2},\ldots ,V_{r-1}$ and $V_{r}$. The sets $V_{1}, V_{2},\ldots ,V_{r-1}$ and $V_{r}$ are called the partite sets of G. A 2-partite graph is often said to be a bipartite graph.

Due to their numerous applications, domination and its variations in graphs have been extensively studied (see [6, 7] for a detailed survey). A subset $D\subseteq V(G)$ is called a dominating set of G if every vertex in V(G) is either in D or adjacent to at least one vertex in D. A subset $D\subseteq V(G)$ is called a total dominating set of G if every vertex in V(G) is adjacent to at least one vertex in D. The (total )domination number $\gamma (G)$ ($\gamma _{t}(G)$) of G is the cardinality of the smallest (total) dominating set of G. To find a smallest (total) dominating set of a graph is called the (total) dominating set problem.

Wang et al. [12] introduced the concept of positive influence domination in graphs. A positive influence dominating set (PIDS) of a graph G is a subset $D\subseteq V(G)$ such that every vertex $v\in V(G)$ has at least half of its neighbors in D. The positive influence domination number $\gamma _{PI}(G)$ of G is the cardinality of the smallest PIDS of G. The PIDS problem aims to find a smallest PIDS of a graph. An important application of the PIDS in social networks is described in [13]. Usually, a social network can be modeled as a graph with a set of vertices (nodes) representing individuals and edges representing some certain type of relationship between individuals, and individuals tend to be affected by the opinions (behaviors) of their family and peers. The PIDS problem was considered to intervene social problems such as drinking and drug-related issues. An individual can be converted to one holding positive opinion through some interventions and education programs and have positive influence on his friends, and an individual is also more inclined to hold positive opinion if more of his friends have positive opinion. On the other hand, an individual whose initial opinion is positive can be converted to one with negative opinion and influence his friends negatively if many of his friends hold negative opinion. Due to the limitation of education resources, instead of choosing every individual with negative opinion to participate in the intervention program, it might be reasonable to choose a PIDS of all of the people holding negative opinion to ensure that the intervention can produce a globally positive influence on the entire social network.

Most of research results on PIDS problem in the literature focus on studying its complexity and approximation algorithm for various graph classes. The PIDS problem is proved to be NP-hard in general graphs by Wang et al. [12]. The first approximation algorithm for PIDS problem is given by Wang et al. [13], in which the authors design a greedy algorithm with $H(\Delta )$ approximation ratio and $O(n^{3})$ time complexity by using submodular functions, where H is the harmonic function and n is the order of input graph, while they also investigate the hardness of approximation of PIDS problem and show that it is APX-hard. However, Raei et al. [11] present a new greedy algorithm for PIDS problem which has outstanding time complexity of $O(n^{2})$ compared with that of wang’s algorithm [13]. Later, Zhang et al. [14] propose a greedy algorithm with constant approximation ratio for PIDS problem in power-law graphs. Dinh et al. [4] continue to study the approximability of PIDS problem, and they prove that PIDS problem cannot be approximated within factors of $ln\Delta -O(lnln\Delta )$ and $(\frac{1}{2}-o(1))lnn$, unless $\mathrm P=NP$ and $\mathrm NP\subset DTIME(n^{O(loglogn)})$, respectively. Furthermore, for a dense graph G with $|E(G)|=\Omega (|V(G)|^{2})$, the authors [4] show that there exists an algorithm with constant approximation ratio for PIDS problem, in addition, they give a linear-time algorithm to solve PIDS problem in trees which has better running time than that of the $O(n^{2})$ dynamic programming algorithm in Cicalese et al. [2].

The rest of this paper is structured as follows. In Sect. 2, we establish some sharp lower bounds on $\gamma _{PI}(G)$. In Sect. 3, we show that the decision version of PIDS problem is NP-complete on bipartite graphs and split graphs. Finally, Sect. 4 ends the paper by proving PIDS problem on graphs with maximum degree 3 remains APX-complete.

2 Lower bounds on Positive Influence Domination Number

In this section, we first present a sharp lower bound on positive influence domination number for a general graph in terms of its size, maximum degree and the number of odd vertices.

Theorem 1

If G is a graph of size m with maximum degree $\Delta$ and $n_{o}$ odd vertices, then

$$\begin{aligned} \gamma _{PI}(G)\ge \left\lceil \frac{2m+n_{o}}{2\Delta }\right\rceil , \end{aligned}$$

and this bound is sharp.

Proof

Let D be a $\gamma _{PI}(G)$-set, which is PIDS of the graph G with cardinality $\gamma _{PI}(G)$, and $S=V\setminus D$. We write $V_{o}=\{v\in V~|~d(v)~ \text{ is } \text{ odd }\}$ and $V_{e}=\{v\in V~|~d(v)~ \text{ is } \text{ even }\}$. Let $D_{o}=D\cap V_{o}, D_{e}=D\cap V_{e}, S_{o}=S\cap V_{o}, S_{e}=S\cap V_{e}$ and $|V_{0}|=n_{o}$. By counting the number of edges in [S, D], we have

$$\begin{aligned} e(S,D)=\sum _{v\in D}|N(v)\cap S|= & {} \sum _{v\in D}(d(v)-|N(v)\cap D|)\nonumber \\\le & {} \sum _{v\in D}d(v)-\sum _{v\in D}\left\lceil \frac{d(v)}{2}\right\rceil \nonumber \\= & {} \sum _{v\in D}d(v)-\sum _{v\in D_{o}}\frac{d(v)+1}{2}-\sum _{v\in D_{e}}\frac{d(v)}{2}\nonumber \\= & {} \sum _{v\in D}d(v)-\frac{1}{2}\sum _{v\in D}d(v)-\frac{1}{2}|D_{o}|\nonumber \\= & {} \frac{1}{2}\sum _{v\in D}d(v)-\frac{1}{2}|D_{o}|. \end{aligned}$$

(1)

and

$$\begin{aligned} e(S,D)=\sum _{v\in S}|N(v)\cap D|\ge & {} \sum _{v\in S}\left\lceil \frac{d(v)}{2}\right\rceil =\sum _{v\in S_{o}}\frac{d(v)+1}{2}+\sum _{v\in S_{e}}\frac{d(v)}{2}\nonumber \\= & {} \frac{1}{2}\sum _{v\in S}d(v)+\frac{1}{2}|S_{o}|. \end{aligned}$$

(2)

According to (1) and (2), we obtain

$$\begin{aligned} \sum _{v\in S}d(v)+|S_{o}|\le 2e(S,D)\le \sum _{v\in D}d(v)-|D_{o}| \end{aligned}$$

or equivalently

$$\begin{aligned} \sum _{v\in S}d(v)+n_{o}\le \sum _{v\in D}d(v). \end{aligned}$$

Thus,

$$\begin{aligned} 2m+n_{o}=\sum _{v\in V}d(v)+n_{o}\le 2\sum _{v\in D}d(v)\le 2|D|\Delta , \end{aligned}$$

and so $\gamma _{PI}(G)\ge \left\lceil \frac{2m+n_{o}}{2\Delta }\right\rceil$.

To see that the bound in Theorem 1 is sharp, we consider the graph $G_{a,b}$ constructed as follows. For positive integers a and b satisfying $a+1\le b\le 2a+1$, let $G_{a,b}$ be the graph with vertex set $A\cup B$, where $|A|=2(a+1)$ and $|B|=2b$. The edge set of $G_{a,b}$ is formed as follows: Add $2b(a+1)$ edges between A and B so that each vertex of A has exactly b neighbors in B, while each vertex of B has precisely $a+1$ neighbors in A. Add edges among vertices in A so that A induces a b-regular graph and add edges among vertices in B so that B induces a a-regular graph (since $b<2(a+1)$ and $a<2b$, it follows that such additions of edges are possible). By construction, $G_{a,b}$ is a graph of size $m=ab+3b(a+1)$ with maximum degree $\Delta =2b$ and $n_{o}=2b$. It is easy to verify that A is a PIDS of $G_{a,b}$ with cardinality $2(a+1)$. Hence, $\gamma _{PI}(G_{a,b})=\left\lceil (2m+n_{o})/2\Delta \right\rceil$. This completes the proof of Theorem 1.$\square$

The following result is an immediate consequence of Theorem 1.

Corollary 2

If G is a k-regular graph of order $n\ge 2$, then

$$\begin{aligned} \gamma _{PI}(G)\ge \left\{ \begin{array}{ll} \lceil \frac{k+1}{2k}n\rceil &{} \text{ for } \text{ k } \text{ odd },\\ \lceil \frac{n}{2}\rceil &{} \text{ for } \text{ k } \text{ even }. \end{array} \right. \end{aligned}$$

We next establish a sharp lower bound on $\gamma _{PI}(G)$ for an r-partite graph G in terms of its order and minimum degree. For this purpose, we begin by stating an useful inequality due to Kang et al. in [8].

Lemma 3

( [8]) For $r~(r\ge 2)$ non-negative integers $m_{1},m_{2},\cdots ,m_{r}$, then

$$\begin{aligned} \sqrt{\left( 2+\frac{2}{r-1}\right) \sum ^{r-1}_{i=1}\sum ^{r}_{j=i+1}m_{i}m_{j}}\le \sum ^{r}_{i=1}m_{i}. \end{aligned}$$

.

Theorem 4

If $G=(V_{1},V_{2},\ldots ,V_{r};E)$ is an r-partite graph of order n with minimum $\delta (G)\ge 1$, $r\ge 2$, then

$$\begin{aligned} \gamma _{PI}(G)\ge -\frac{r\delta }{4(r-1)}+\sqrt{\left( \frac{r\delta }{4(r-1)}\right) ^{2}+\frac{r\delta }{2(r-1)}n}, \end{aligned}$$

and this bound is sharp.

Proof

Let D and S be defined as in the proof of Theorem 1. For $1\le i\le r$, we define $D_{i}=D\cap V_{i}$ and $S_{i}=S\cap V_{i}$. Furthermore, set $|D|=d$, $|S|=s$, $|D_{i}|=d_{i}$ and $|S_{i}|=s_{i}$. Then,

$$\begin{aligned} \sum ^{r}_{i=1}d_{i}+\sum ^{r}_{i=1}s_{i}=d+s=n. \end{aligned}$$

(3)

Firstly, we get

$$\begin{aligned} e(S,D)=\sum _{v\in S}|N(v)\cap D|\ge & {} \sum _{v\in S}\left\lceil \frac{d(v)}{2}\right\rceil =\sum _{i=1}^{r}\sum _{v\in S_{i}}\left\lceil \frac{d(v)}{2}\right\rceil \nonumber \\\ge & {} \frac{\delta }{2}\sum _{i=1}^{r}s_{i}=\frac{\delta }{2}s. \end{aligned}$$

(4)

On the other hand,

$$\begin{aligned} e(S,D)= & {} \sum _{v\in D}|N(v)\cap S|=\sum _{i=1}^{r}\sum _{v\in D_{i}}|N(v)\cap S|\nonumber \\\le & {} \sum _{i=1}^{r}\sum _{v\in D_{i}}|N(v)\cap D|\nonumber \\\le & {} \sum _{i=1}^{r}\sum _{v\in D_{i}}(|D|-|D_{i}|)=\sum _{i=1}^{r}d_{i}(|D|-|D_{i}|)\nonumber \\= & {} \sum _{i=1}^{r}(d_{i}\sum _{j=1,j\ne i}^{r}d_{j})=2\sum _{i=1}^{r-1}\sum _{j=i+1}^{r}d_{i}d_{j}. \end{aligned}$$

(5)

By Lemma 3, it follows from (5) that

$$\begin{aligned} e(S,D)\le 2\sum _{i=1}^{r-1}\sum _{j=i+1}^{r}d_{i}d_{j}\le \frac{r-1}{r}\left( \sum _{i=1}^{r}d_{i}\right) ^{2}=\frac{r-1}{r}d^{2}. \end{aligned}$$

(6)

Combining (3), (4) and (6), we obtain $(\delta /2)(n-d)\le (r-1)d^{2}/r$, i.e., $2(r-1)d^{2}+r\delta d-r\delta n\ge 0$. Therefore,

$$\begin{aligned} \gamma _{PI}(G)=|D|=d\ge -\frac{r\delta }{4(r-1)}+\sqrt{\left( \frac{r\delta }{4(r-1)}\right) ^{2}+\frac{r\delta }{2(r-1)}n}. \end{aligned}$$

The sharpness of the bound in Theorem 4 may be seen as follows. For even integer $r\ge 2$ and integer $t\ge 1$, let F be a graph that is isomorphic to t disjoint copies of $K_{1,(r-1)t}$, and let $F_{1},F_{2},\ldots , F_{r}$ be r disjoint copies of F. Moreover, for $1\le i\le r$, we denote the sets of vertices of degree 1 and $(r-1)t$ in $F_{i}$ by $X_{i}=\{x^{i}_{1},x^{i}_{2},\cdots ,x^{i}_{(r-1)t^{2}}\}$ and $Y_{i}$, respectively. Now, let G be the graph obtained from the disjoint union of $F_{1},F_{2},\ldots , F_{r}$ by connecting each vertex of $Y_{i}$ to each vertex of $Y_{j}$, for $1\le i<j\le r$, and joining $x^{i}_{k}$ to $x^{i+1}_{k}$, for $i=1,3,\ldots , r-1$, $k=1,2,\ldots ,(r-1)t^{2}$. Thus, G is an r-partite graph of order $n=rt+r(r-1)t^{2}$ with partite sets $X_{1}\cup Y_{2},X_{2}\cup Y_{3},\ldots ,X_{r-1}\cup Y_{r},X_{r}\cup Y_{1}$. Clearly, the minimum degree $\delta$ of G is 2, and each vertex of $\cup ^{r}_{i=1}X_{i}$ has degree 2, while each vertex of $\cup ^{r}_{i=1}Y_{i}$ has degree $2(r-1)t$. It is not hard to verify that $\cup ^{r}_{i=1}Y_{i}$ is a PIDS of G. Hence,

$$\begin{aligned} \gamma _{PI}(G)\le \sum _{i=1}^{r}|Y_{i}|=rt= -\frac{r\delta }{4(r-1)}+\sqrt{\left( \frac{r\delta }{4(r-1)}\right) ^{2}+\frac{r\delta }{2(r-1)}n}, \end{aligned}$$

and so

$$\begin{aligned} \gamma _{PI}(G)= -\frac{r\delta }{4(r-1)}+\sqrt{\left( \frac{r\delta }{4(r-1)}\right) ^{2}+\frac{r\delta }{2(r-1)}n}. \end{aligned}$$

This completes the proof of Theorem 4.$\square$

3 NP-Completeness Results of Positive Influence Domination Problem

In this section, we will show that the decision version of the PIDS problem is NP-complete on bipartite graphs and split graphs. The decision version of the PIDS problem is denoted by PIDOM.

Positive Influence Domination Problem (PIDOM)

Instance: A graph $G=(V,E)$ and a positive integer $k\le |V|$.

Question: Does G have a PIDS of cardinality at most k?

To show that PIDOM is NP-complete on bipartite graphs, we shall use a transformation of the well-known total domination problem (TDOM) which is NP-complete on bipartite graphs [9].

Total Domination Problem (TDOM)

Instance: A graph $G=(V,E)$ and a positive integer $k\le |V|$.

Question: Does G have a total dominating set of cardinality at most k?

Theorem 5

PIDOM is NP-complete on bipartite graphs.

Proof

Clearly, PIDOM belongs to NP, since we can check in polynomial time whether or not a set of vertices is a PIDS of a graph. We now show the NP-hardness of PIDOM on bipartite graphs by transforming TDOM on bipartite graphs to it in polynomial time.

Given a bipartite graph $G=(V,E)$ with $V=\{v_{1},v_{2},\ldots ,v_{n}\}$ and $|E|=m$, let the graph H arise from G by adding to each vertex $v_{i}\in V$ a set of $(d_{G}(v_{i})-1)$ paths of length three, say $P_{i}=v_{i}x_{i,j}y_{i,j}z_{i,j}$ for $1\le i\le n$ and $1\le j\le d_{G}(v_{i})-1$. Let $X_{i}=\{x_{i,j}|1\le j\le d_{G}(v_{i})-1\}$, $Y_{i}=\{y_{i,j}|1\le j\le d_{G}(v_{i})-1\}$ and $Z_{i}=\{z_{i,j}|1\le j\le d_{G}(v_{i})-1\}$ for $1\le i\le n$. Thus, $V(H)=V\cup (\cup _{i=1}^{n} \{X_{i},Y_{i},Z_{i}\})$ and $E(H)=E\cup (\cup _{i=1}^{n} \{v_{i}x_{i,j},x_{i,j}y_{i,j},y_{i,j}z_{i,j}| 1\le j\le d_{G}(v_{i})-1\})$. Note that the graph H is a bipartite graph of order $6m-2n$ and size $7m-3n$. Moreover, the construction of H can be finished in polynomial time. We next show that G has a total dominating set of cardinality at most k if and only if H has a PIDS of cardinality at most $k+4m-2n$.

Suppose that G has a total dominating set D with $|D|\le k$. Then, it is easy to verify that $D\cup (\cup _{i=1}^{n} \{X_{i},Y_{i}\})$ is a PIDS of H of cardinality at most $k+4m-2n$.

On the other hand, assume that H has a PIDS S of cardinality at most $k+4m-2n$ such that $|S\cap Z_{i}|$ is minimized for each $1\le i\le n$. Since $z_{i,j}$ has only one neighbor $y_{i,j}$ in H, then $\cup _{i=1}^{n}Y_{i}\subseteq S$. We can claim that $|S\cap Z_{i}|=0$ for each $1\le i\le n$. Otherwise, suppose that there is a vertex $z_{i,j}\in S$. Let $S^{\prime }=(S\setminus \{z_{i,j}\})\cup \{x_{i,j}\}$. Then, it is not hard to see that $S^{\prime }$ is a PIDS of H with $|S^{\prime }|\le k+4m-2n$ and $|S^{\prime }\cap Z_{i}|<|S\cap Z_{i}|$, contradicting to our choice of S. To dominate $y_{i,j}$, we have $\cup _{i=1}^{n}X_{i}\subseteq S$. Let $D=S\cap V(G)$. Then, it follows that $v_{i}$ is adjacent to at least one vertex of D because $d_{H}(v_{i})=2d_{G}(v_{i})-1$ for each $1\le i\le n$. Therefore, D is a total dominating set of G satisfying $|D|=|S|-|\cup _{i=1}^{n}\{X_{i},Y_{i}\}|\le k$. This completes the proof of Theorem 5.$\square$

We next show that PIDOM is NP-complete on split graphs by giving a polynomial time reduction from a classic NP-complete problem, namely the vertex cover problem [5]. A subset C of vertices is a vertex cover of a graph G if every edge in G has at least one endpoint in C. The vertex cover problem is to seek a vertex cover of minimum cardinality of G.

Vertex Cover (VC)

Instance: A graph $G=(V,E)$ and a nonnegative integer $k\le |V|$.

Question: Does G have a vertex cover of cardinality at most k?

Theorem 6

PIDOM is NP-complete on split graphs.

Proof

Obviously, PIDOM is in NP. To show that PIDOM is NP-hard on split graphs, we establish a polynomial time reduction from VC to it. Let $G=(V,E)$ be an instance of VC, where the maximum degree of G is $\Delta$. We construct the graph $H=(V(H),E(H))$ with vertex set $V(H)=V\cup V_{E}\cup X\cup Y$, where $V_{E}=\{v_{e}|e\in E\}$, $X=\{x_{1},x_{2},\ldots ,x_{n},x_{n+1},\ldots , x_{n+\Delta }\}$, $Y=\{y_{1},y_{2},\ldots ,y_{n},y_{n+1},\ldots , y_{n+\Delta }\}$, and the edge set $E(H)= \{vv_{e}| v\in V, v_{e}\in V_{E}~ \text{ and }~ v\in e\}\cup \{x_{i}y_{i}| 1\le i \le n\}\cup \{uv| u,v\in V\cup X, u\ne v\}$. Clearly, H is a split graph whose vertex set V(H) can be partitioned into an independent set $Y\cup V_{E}$ and a clique $V\cup X$, and the construction of H can be accomplished in polynomial time.

We next show that G has a vertex cover of cardinality at most k if and only if H has a PIDS of cardinality at most $k+n+\Delta$.

Suppose first G has a vertex cover C of cardinality at most k. Let $S=C\cup X$. Note that $d_{H}(v_{e})=2$ and $v_{e}$ has at least one neighbor in C for each $v_{e}\in V_{E}$. Also, each $y_{i}\in Y$ has only one neighbor $x_{i}$ in X. Since $d_{H}(v)=2n+\Delta -1+d_{G}(v)$ for each $v\in V$ and $d_{H}(x_{i})=2n+\Delta$ for each $x_{i}\in X$, we obtain $\lceil d_{H}(v)/2\rceil \le \lceil (2n+2\Delta -1)/2\rceil \le n+\Delta$ and $\lceil d_{H}(x_{i})/2\rceil \le n+\Delta \le n+\Delta +k-1$. Thus, each $v\in V$ has at least half of its neighbors in S, so does $x_{i}\in X$. This means that S is a PIDS of H of cardinality $|S|\le k+n+\Delta$.

On the other hand, assume that H has a PIDS S of cardinality at most $k+n+\Delta$ such that $|S\cap (Y\cup V_{E})|$ is minimum. Obviously, $X\subseteq S$ in order to positively dominate each vertex of Y. Let $C=S\cap V$. Then, for each $v_{e} \in V_{E}$, $|N_{H}(v_{e})\cap C|\ge 1$ as $d_{H}(v_{e})=2$. This implies that C is a vertex cover of G. If $|S\cap (Y\cup V_{E})|\ge 1$, then $S^{\prime }=S\setminus (S\cap (Y\cup V_{E}))$ is also a PIDS of H by a similar argument above. However, $|S^{\prime }\cap (Y\cup V_{E})|\le S\cap (Y\cup V_{E})|-1$, which is a contradiction to our assumption. Hence, $|S\cap (Y\cup V_{E})|=0$, and so C is a vertex cover of G of cardinality at most k. This completes the proof of Theorem 6.$\square$

4 APX-Completeness of Positive Influence Domination Problem

In this section, we will investigate the APX-completeness of PIDS problem for bounded degree graphs. To our aim, we need the following result obtained by Wang et al. [13].

Theorem 7

( [13]) The PIDS problem for a graph with maximum degree $\bigtriangleup$ can be approximated within an approximation ratio of $H(\Delta )$, where $H(\Delta )$ is the harmonic function, i.e., $H(\Delta )=\sum _{i=1}^{\Delta }\frac{1}{i}\le 1+\ln \Delta$.

By Theorem 7, the PIDS problem can be approximated within a constant ratio if the degree of the graph is bounded by a constant. So the PIDS problem for bounded degree graphs belongs to APX. In [13], Wang et al. also proved that the PIDS problem is APX-hard, in fact, the graph constructed in the proof of APX-hardness has maximum degree 6. Thus, the PIDS problem is APX-completeness for graphs with maximum degree 6. Next, we show that the problem is still APX-complete for graphs with maximum degree 3. Before giving our proof, let us recall the concept of L-reduction defined as follows [1, 10].

Given two NP-optimization problems $\Pi _{1}$ and $\Pi _{2}$ and a polynomial time transformation f from instances of $\Pi _{1}$ to instances of $\Pi _{2}$, f is said to be an L-reduction if there are two positive constants $\alpha$ and $\beta$ such that for every instance x of $\Pi _{1}$:

• 1. $opt_{\Pi _{2}}(f(x))\le \alpha \cdot opt_{\Pi _{1}}(x)$;

• 2. for every feasible solution y of f(x) with objective value $m_{\Pi _{2}}(f(x),y)=c_{2}$, we can in polynomial time find a solution $y^{\prime }$ of x with $m_{\Pi _{1}}(x,y^{\prime })=c_{1}$ satisfying $|opt_{\Pi _{1}}(x)-$ $c_{1}|\le \beta \cdot |opt_{\Pi _{2}}(f(x))-c_{2}|$.

Theorem 8

The PIDS is APX-complete on graphs with maximum degree 3.

Proof

By Theorem 7, the PIDS problem is included in APX for bounded degree graphs. It is well known that the vertex cover problem is APX-complete for cubic graphs [3]. To complete the proof of our theorem, it suffices that we present an L-reduction f from instances of the vertex cover problem for cubic graphs to the instances of the PIDS problem on graphs with maximum degree 3. Given a cubic graph $G=(V,E)$ with $V=\{v_{1},v_{2},\ldots ,v_{n}\}$ and $E=\{e_{1},e_{2},\ldots ,e_{m}\}$, the graph $G^{\prime }=(V^{\prime },E^{\prime })$ is constructed in the following way:

• For each vertex $v_{i}\in V$ and each edge $e_{j}\in E$, we associate two vertices named $v_{i}$    and $v_{e_{j}}$, respectively.

• For each vertex $v_{e_{j}}$, we attach a path $P_{j}=v_{e_{j}}x_{e_{j}}y_{e_{j}}$.

• Joining the vertex $v_{i}$ to the vertex $v_{e_{j}}$ if and only if the vertex $v_{i}$ is incident to the    edge $e_{j}$ in G.

For notation convenience, let $V_{E}=\cup _{j=1}^{m}v_{e_{j}}$, $X=\cup _{j=1}^{m} x_{e_{j}}$ and $Y=\cup _{j=1}^{m} y_{e_{j}}$. Thus, $V^{\prime }=V\cup V_{E}\cup X\cup Y$. By the above construction, it is clear to see that $G^{\prime }$ is of maximum degree 3 and the construction is accomplished in polynomial time.

Claim G has a vertex cover of cardinality at most k if and only if $G^{\prime }$ has a PIDS of cardinality at most $k+3n$.

Suppose first G has a a vertex cover C with $|C|\le k$. It is easy to check that $C\cup \ V_{E}\cup \ X$ is a PIDS of $G^{\prime }$ of cardinality at most $k+3n$ as G is cubic.

On the other hand, assume that S is a PIDS of $G^{\prime }$ with $|S|\le k+3n$. Obviously, $X\subseteq S$ because each $y_{e_{j}}\in Y$ has only one neighbor in X. To positively dominate $x_{e_{j}}$, at least one of $v_{e_{j}}$ and $y_{e_{j}}$ belongs to S. If $y_{e_{j}}\in S$ for some $1\le j\le m$, then $(S\setminus \{y_{e_{j}}\})\cup \{v_{e_{j}}\}$ is also a PIDS of $G^{\prime }$ with cardinality at most |S|. Hence, we may assume that S contains all vertices of $V_{E}$ and does not include any vertex of Y. Let $C=S\cap V$. Then, we have $|C|\le k$ since $S\setminus C=V_{E}\cup X$. Notice that each $v_{e_{j}}\in V_{E}$ has degree precisely 3 in $G^{\prime }$ and already has one neighbor $x_{e_{j}}\in S$. Hence, $v_{e_{j}}$ must have at least one neighbor in C, and so at least one of two endpoints of $e_{j}$ lies in C. This implies that C is a vertex cover of G. This completes the proof of Claim.

Let $C^{*}$ and $S^{*}$ be a minimum vertex cover of G and a minimum PIDS of $G^{\prime }$, respectively. Then, we have $|S^{*}|=|C^{*}|+3n$ by Claim. Since G is cubic, each vertex of $C^{*}$ can cover at most 3 edges of G, and hence, $|C^{*}|\ge m/3= n/2$. So $|S^{*}|=|C^{*}|+3n\le 7|C^{*}|$. For the converse, let S be any PIDS of $G^{\prime }$. From the proof of Claim, we can in polynomial time establish a vertex cover $C=S\cap V$ of G with cardinality $|C|\le |S|-3n$. Hence, $|C|-|C^{*}|\le |S|-|S^{*}|$. Therefore, f is an L-reduction with $\alpha =7$ and $\beta =1$. This completes the proof of Theorem 8.$\square$