Research on investment evaluation of highway projects based on system dynamics model

1.   Introduction

Throughout this paper, all graphs considered are finite, undirected, loopless and without multiple edges. We refer the reader to ^[3,18] for terminology and notation in graph theory.

Let $G = (V, E)$ be a graph of order $n$ with vertex set $V(G)$ and edge set $E(G)$. The open neighborhood of a vertex $v$ in $G$ is $N_G(v) = N(v) = \{u\in V(G)|uv\in E(G)\}$, and the closed neighborhood of $v$ is $N_G[v] = N[v] = N(v)\cup\{v\}$. The degree of a vertex $v$ in the graph $G$ is $d_G(v) = d(v) = |N(v)|$. Let $\delta(G) = \delta$ and $\Delta(G) = \Delta$ denote the minimum and maximum degree of a graph $G$, respectively. Denote by $G[H]$ the induced subgraph of $G$ induced by $H$ with $H\subset V(G)$. A vertex $v$ in $G$ is a $leaf$ if $d(v) = 1$. A vertex $u$ is a $support$ $vertex$ if $u$ has a leaf neighbor. Denote $L(u) = \{v|uv\in E(G), d(v) = 1\}$.

A subset $M\subseteq E(G)$ is called a matching in $G$ if no two elements are adjacent in $G$. A vertex $v$ is said to be $M$-saturated if some edges of $M$ are incident with $v$, otherwise, $v$ is $M$-unsaturated. If every vertex of $G$ is $M$-saturated, the matching $M$ is perfect. $M$ is a maximum matching if $G$ has no matching $M'$ with $|M'| > |M|$. Let $R$ be a subgraph of $G$, $M$ be a matching of $G$, $v\in V(R)$, $uv\in M$. We say the vertex $v$ is $R^I$ (resp. $R^O$) if $u\in V(R)$ (resp. $u\notin V(R)$).

A set $VC$ of vertices in a graph $G$ is a vertex cover of $G$ if all the edges are touched by the vertices in $VC$. A vertex cover $VC$ of $G$ is minimal if no proper subset of it is a vertex cover of $G$. A minimal vertex cover of maximum cardinality is called a $VC$-set. In 2001, Mishra et al. ^[13] denote by $MAX$-$MIN$-$VC$ the problem of finding a $VC$-set of $G$. Bazgan et al. ^[2] showed that $MAX$-$MIN$-$VC$ is APX-complete for cubic graphs.

A set $PD\subseteq V(G)$ in a graph $G$ is a paired dominating set if every vertex $v\notin PD$ is adjacent to a vertex in $PD$ and the subgraph induced by $PD$ contains a perfect matching. Paired domination was proposed in 1996 ^[9] and was studied for example in ^{[4,5,6,12,16,17]}. A paired dominating set $PD$ of $G$ is minimal if there is no proper subset $PD'\subset PD$ which is a paired dominating set of $G$. A minimal paired dominating set with maximum cardinality is called a $\Gamma_{pr}(G)$-set. The upper paired domination number of $G$ is the cardinality of a $\Gamma_{pr}(G)$-set of $G$. Denote by $Upper$-$PDS$ the problem of finding a $\Gamma_{pr}(G)$-set of $G$. Upper paired domination was introduced by Dorbec et al. in ^[7]. They investigated the relationship between the upper total domination and upper paired domination numbers of a graph. Later, they established bounds on upper paired domination number for connected claw-free graphs^[10]. Denote $Pr(v) = \{u|u\notin PD, N(u)\cap PD = \{v\}, uv\in E(G)\}$, where $PD$ is a minimal paired dominating set of $G$.

Recently, Michael et al. showed that $Upper$-$PDS$ is NP-hard for split graphs and bipartite graphs, and APX-completeness of $Upper$-$PDS$ for bipartite graphs with $\Delta = 4$ in ^[11]. In order to improve the results in ^[11], we show that $Upper$-$PDS$ is APX-complete for bipartite graphs with $\Delta = 3$.

2.   APX-completeness

The class APX is the set of NP-optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant.

First, we recall the notation of $L$-reduction ^[1,15]. Given two NP-optimization problems $H$ and $G$ and polynomial time transformation $f$ from instances of $H$ to instances of $G$, we say that $f$ is an $L$-reduction if there are positive constants $\alpha$ and $\beta$ such that for every instance $x$ of $H$:

(i) $opt_G(f(x))\leq \alpha opt_H(x)$;

(ii) for every feasible solution $y$ of $f(x)$ with objective value $m_G(f(x), y) = a$, we can find a solution $y'$ of $x$ with $m_H(x, y') = b$ in polynomial time such that $|opt_H(x)-b|\leq \beta|opt_G(f(x))-a|$.

To show that a problem $P\in APX$ is APX-complete, it's enough to show that there is an $L$-reduction from some APX-complete problems to $P$.

Denote by $MAX$-$MIN$-$VC$ the problem of finding a maximum minimal vertex cover of $G$. Note that, Minimum Domination problem is APX-complete even for bipartite graphs with maximum degree 3 ^[14], and Minimum Independent Domination problem ^[8] is the complement problem of $MAX$-$MIN$-$VC$ in a graph $G$. We can obtain an $L$-reduction from Minimum Domination problem to Minimum Independent Domination problem by replacing every edge $uv$ with a path $P_{uv} = uabcv$ with $\alpha = 7$, $\beta = 1$. It's clear that Minimum Independent Domination problem and $MAX$-$MIN$-$VC$ are in APX. Thus, Minimum Independent Domination problem is APX-complete even for bipartite graphs with maximum degree 3, so is $MAX$-$MIN$-$VC$ (by Theorem 7 in ^[2]).

In this section, we show $Upper$-$PDS$ for bipartite graphs with maximum degree 3 is APX-complete by providing an $L$-reduction $f$ from $MAX$-$MIN$-$VC$ for bipartite graphs with maximum degree 3.

We formalize the optimization problems as follows.

Lemma 1. ^[11] $Upper$-$PDS$ can be approximated with a factor of $2\Delta$ for graphs without isolated vertices and with maximum degree $\Delta$.

Therefore, $Upper$-$PDS$ is in APX.

Let $G = (V, E)$ be a bipartite graph with $|E| = m$, $\Delta(G) = 3$.

For each edge $xy\in E(G)$, let $H_{xy}$ be the graph which is shown in Figure 1. Let $T_1 = \{$ $a, ..., a_5,$ $b, ..., b_5,$ $r, ..., r_6,$ $s, ..., s_6,$ $c, .., c_3,$ $u, u_1, v, v_1\}$, $T_2 = \{p, ..., p_6,$ $q, ..., q_6,$ $d, ..., d_3, w, z\}$, $T_3 = \{h, .., h_5\}$, $T_4 = \{t, ..., t_5\}$, $V(H_{xy}) =$$V(T_1)\cup V(T_2)\cup V(T_3)\cup V(T_4)\cup \{w_1, z_1, x, y\}$, $|V(H_{xy})| = 70$.

Construct $G'$ by replacing each edge $xy\in E(G)$ with the graph $H_{xy}$.

It's clear, $\Delta(G') = 3$ and $G'$ is a bipartite graph.

Let $S_p = \{p, p_1, ..., p_6\}$, $S_q = \{q, q_1, ..., q_6\}$, $S_a = \{a, a_1, ..., a_5\}$, $S_b = \{b, b_1, ..., b_5\}$, $S_r = \{r, r_1, ..., r_6\}$, $S_s = \{s, s_1, ..., s_6\}$, $S_c = \{c, c_1, c_2, c_3\}$, $S_d = \{d, d_1, d_2, d_3\}$.

Let $xy = e\in E(G)$, $H_{e}' = H_{xy}' = H_{xy}-\{x, y\}$, $|V(H_{xy}')| = 68$.

Let $PD$ be a paired dominating set of $G'$, $uv\in E(G)$. We say $H_{uv}'$ is $[I, O]$ if $u$ is $H_{uv}^I$ and $v$ is $H_{uv}^O$, or if $v$ is $H_{uv}^I$ and $u$ is $H_{uv}^O$. We say $H_{uv}'$ is $[I, 0]$ if $u$ is $H_{uv}^I$ and $v\notin PD$, or if $u\notin PD$ and $v$ is $H_{uv}^I$. Analogously, $H_{uv}'$ could be $[0, 0]$ ($[I, I]$ or $[O, O]$ or $[O, 0]$).

Note that

The following lemma is immediate.

Lemma 2. Let $PD$ be a minimal paired dominating set of $G$, $M$ be a perfect matching of $G[PD]$. If $v, u$ are support vertices, $uv\in E(G)$, $x\in L(v)$, $y\in L(u)$, then $|\{x, y\}\cap PD|\leq 1$.

Lemma 3. Let $PD$ be a minimal paired dominating set of $G'$, $M$ be a perfect matching of $G'[PD]$. For each $H_{xy}$, we have

(a) $|S_c\cap PD| = 4$ if and only if $r, s\notin PD$, $Pr(c_3)\neq \emptyset$ or $Pr(c)\neq \emptyset$.

(b) $|S_d\cap PD| = 4$ if and only if $p, q \notin PD$, $Pr(d_3)\neq \emptyset$ or $Pr(d)\neq \emptyset$.

(c) $|T_3\cap PD|\leq 4$ with equality if and only if (i) or (ii) holds,

(i) $Pr(h_1)\neq \emptyset$ if $h\notin PD$,

(ii) $N(h)\cap PD = \{h_1\}$ or $Pr(h)\neq \emptyset$ if $h\in PD$.

And if $h$ is $G[T_3]^O$, $|T_3\cap PD| = 3$.

(d) $|T_4\cap PD|\leq 4$ with equality if and only if (i) or (ii) holds,

(i) $Pr(t_1)\neq \emptyset$ if $t\notin PD$,

(ii) $N(t)\cap PD = \{t_1\}$ or $Pr(t)\neq \emptyset$ if $t\in PD$.

And if $t$ is $G[T_4]^O$, $|T_4\cap PD| = 3$.

(e) $|S_a\cap PD|\leq 4$ with equality if and only if (i) or (ii) holds,

(i) $Pr(a_1)\neq \emptyset$ if $a\notin PD$,

(ii) $N(a)\cap PD = \{a_1\}$ or $Pr(a)\neq \emptyset$ if $a\in PD$.

And if $a$ is $G[S_a]^O$, $|S_a\cap PD| = 3$.

(f) $|S_b\cap PD|\leq 4$ with equality if and only if (i) or (ii) holds,

(i) $Pr(b_1)\neq \emptyset$ if $b\notin PD$,

(ii) $N(b)\cap PD = \{b_1\}$ or $Pr(b)\neq \emptyset$ if $b\in PD$.

And if $b$ is $G[S_b]^O$, $|S_b\cap PD| = 3$.

(g) $3\leq |S_r\cap PD|\leq 4$. And if $r\in PD$ and $r$ is $G[S_r]^O$, $|S_r\cap PD| = 3$.

(h) $3\leq |S_s\cap PD|\leq 4$. And if $s\in PD$ and $s$ is $G[S_r]^O$, $|S_s\cap PD| = 3$.

(i) $3\leq |S_p\cap PD|\leq 4$. And if $p\in PD$ and $p$ is $G[S_p]^O$, $|S_p\cap PD| = 3$.

(j) $3\leq |S_q\cap PD|\leq 4$. And if $q\in PD$ and $q$ is $G[S_q]^O$, $|S_q\cap PD| = 3$.

(k) $|T_2\cap PD|\leq 13$ with equality if and only if $|\{w, z\}\cap PD| = 1$.

(l) $|T_1\cap PD|\leq 22$ with equality if and only if $\{u, v\}\subseteq PD$.

(m) If $\{u, v\}\cap PD = \emptyset$, $|T_1\cap PD|\leq 18$.

Proof. (a) W.l.o.g. we consider $r\in PD$. If $rc\in M$, $|S_c\cap PD|\neq 4$. Otherwise, $c_1c_2, c_3s\in M$ and let $PD' = PD\setminus\{c_1, c_2\}$, $M' = M\setminus\{c_1c_2\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction. If $rc\notin M$, $|S_c\cap PD|\neq 4$. Otherwise, $cc_1, c_2c_3\in M$ and let $PD' = PD\setminus\{c, c_1\}$, $M' = M\setminus\{cc_1\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction.

If $Pr(c_3) = \emptyset$ and $Pr(c) = \emptyset$, let $PD' = PD\setminus\{c, c_3\}$ and $M' = M\setminus\{cc_1, c_2c_3\}\cup \{c_1c_2\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction.

(b) The proof is analogous to that of (a), and the proof is omitted.

(c) Clearly, $|T_3\cap PD|\leq 4$. If $|T_3\cap PD| = 4$, $\{h_1, h_2, h_3, h_4\}\subseteq PD$ or $\{h, h_1, h_2, h_3\}\subseteq PD$. If $\{h_1, h_2, h_3, h_4\}\subseteq PD$, $Pr(h_1)\neq\emptyset$. Otherwise, let $PD' = PD\setminus\{h_4, h_1\}$, $M' = M\setminus\{h_3h_4, h_1h_2\}\cup \{h_2h_3\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction. If $\{h, h_1, h_2, h_3\}\subseteq PD$, $N(h)\cap PD = \{h_1\}$ or $Pr(h)\neq \emptyset$. Otherwise, let $PD' = PD\setminus\{h, h_1\}$, $M' = M\setminus\{hh_1\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction.

If $h$ is $G[T_3]^O$, and since $|T_3\setminus\{h\}\cap PD|$ is even, we have $|T_3\cap PD| = 3$.

(d)–(f) We obtain the conclusions with a similar proof of (c).

(g) Clearly, $3\leq |S_r\cap PD|\neq 6$. If $|S_r\cap PD| = 5$, we obtain $S_r\cap PD = \{r, r_1, r_2, r_3, r_4\}$ or $S_r\cap PD = \{r, r_2, r_3, r_4, r_5\}$ by Lemma 2. Therefore, $PD$ is not a minimal paired dominating set, a contradiction. Thus, $3\leq |S_r\cap PD|\leq 4$.

If $r$ is $G[S_r]^O$, and since $|S_r\setminus\{r\}\cap PD|$ is even, we have $|S_r\cap PD| = 3$.

(k) Since $|S_d\cap PD|\leq 4$, $|T_2\cap PD|\leq 14$ by (i)–(j) and Eq (2.1).

If $|\{w, z\}\cap PD| = 0$, $|T_2\cap PD|\leq 12$.

If $|\{w, z\}\cap PD| = 1$, $|T_2\cap PD|\leq 13$.

Then we consider $|\{w, z\}\cap PD| = 2$. If $w$ is $G[T_2]^I$ or $z$ is $G[T_2]^I$, we may assume $w$ is $G[T_2]^I$. We obtain $wp\in M$, $|S_p\cap PD| = 3$ by (i), $|S_d\cap PD|\leq 3$ by (b). Therefore, $|T_2\cap PD|\leq 12$ by Eq (2.1). If $w, z$ are $G[T_2]^O$, $|S_d\cap PD|\leq 3$ by (b). Since $|T_2\cap PD|$ is even, $|T_2\cap PD|\leq 12$ by Eq (2.1).

Thus, $|T_2\cap PD|\leq 13$ with equality if and only if $|\{w, z\}\cap PD| = 1$, see Figure 2 (a).

(h)–(j) Using similar arguments of (g), the conclusions follow.

(l)–(m) We discuss the following cases.

Case 1. $|\{u, v\}\cap PD| = 2$.

In this case, we have $|\{u_1, v_1\}\cap PD|\geq 1$, $|S_a\cap PD|\geq 3$ and $|S_c\cap PD|\geq 3$, otherwise, $|T_1\cap PD|\leq 22$ by (e)–(h) and Eq (2.2).

W.l.o.g. we assume $u_1\in PD$.

First, we assume that $|S_a\cap PD| = 4$. We obtain $aa_1, uu_1\in M$, $\{r, c, r_1\}\cap PD = \emptyset$ by (e). Thus, $|S_c\cap PD|\leq 3$. Then, we consider $|S_c\cap PD| = 3$, that is, $c_3s\in M$. By (h), we have $|S_s\cap PD| = 3$. Therefore, $|T_1\cap PD|\leq 22$ by Eq (2.2).

Then, we consider $|S_a\cap PD| = 3$. Therefore, $v_1\in PD$, otherwise, $|T_1\cap PD|\leq 22$ by Eq (2.2).

We have $|S_b\cap PD| = 4$, otherwise, $|T_1\cap PD|\leq 22$ by Eq (2.2). By (f), $\{s, s_1, c_3\}\cap PD = \emptyset$. Thus, $|S_c\cap PD|\leq 3$. Therefore, $|T_1\cap PD|\leq 22$ by Eq (2.2), see Figure 2 (b).

Case 2. $|\{u, v\}\cap PD| = 1$.

W.l.o.g. we assume $u\in PD$.

We have $|\{u_1, v_1\}\cap PD|\geq 1$ and $|S_a\cap PD|\geq 3$, otherwise, $|T_1\cap PD|\leq 21$ by Eq (2.2).

Case 2.1 $u_1\in PD$.

If $|S_a\cap PD| = 4$, $\{r, r_1, c\}\cap PD = \emptyset$ by (e). Then $|S_c\cap PD|\leq 3$. If $|S_c\cap PD| = 3$, we have $c_3s\in M$, $|S_s\cap PD|\leq 3$ by (h). Therefore, $|T_1\cap PD|\leq 21$ by Eq (2.2). If $|S_c\cap PD| = 2$, $|T_1\cap PD|\leq 21$ by Eq (2.2).

Now we consider $|S_a\cap PD| = 3$. If $v_1\notin PD$, $|T_1\cap PD|\leq 21$ by Eq (2.2). Thus, $v_1\in PD$, that is, $v_1b\in M$. Therefore, $|S_b\cap PD| = 3$ by (f), $|T_1\cap PD|\leq 21$ by Eq (2.2).

Case 2.2 $u_1\notin PD$.

If $v_1\in PD$, $v_1b\in M$. Therefore, $|S_b\cap PD| = 3$ by (f), $|T_1\cap PD|\leq 21$ by Eq (2.2). Thus, $v_1\notin PD$, and $|T_1\cap PD|\leq 21$ by Eq (2.2).

Case 3. $|\{u, v\}\cap PD| = 0$.

In this case, $|T_1\cap PD|$ is even.

Case 3.1 $|\{u_1, v_1\}\cap PD|\geq 1$.

W.l.o.g. we assume $u_1\in PD$. Then $u_1a\in M$, $|S_a\cap PD| = 3$ by (e). If $v_1\notin PD$, $b\in PD$. By (a), $|S_c\cap PD|\leq 3$. Therefore, $|T_1\cap PD|\leq 19$ by Eq (2.2). If $v_1\in PD$, we obtain $v_1b\in M$, $|S_b\cap PD| = 3$ by (f). $|S_c\cap PD|\leq 3$ by (a). Therefore, $|T_1\cap PD|\leq 19$ by Eq (2.2).

Case 3.2 $|\{u_1, v_1\}\cap PD| = 0$.

In this case, $a, b\in PD$. By (a), $|S_c\cap PD|\leq 3$. Therefore, $|T_1\cap PD|\leq 19$ by Eq (2.2).

Note that $|T_1\cap PD|$ is even, so $|T_1\cap PD|\leq 18$, see Figure 2 (c).

Thus, (l) and (m) hold.

Lemma 4. Let $PD$ be a minimal paired dominating set of $G'$.

(a) $|V(H'_{xy})\cap PD|\leq 43$.

(b) If $\{xw_1, yz_1\} \subset M$, $|V(H'_{xy})\cap PD|\leq 42$.

(c) If $\{xw_1, yz_1\} \cap M = \emptyset$ and $\{w_1, z_1\}\subseteq PD$, $|V(H'_{xy})\cap PD|\leq 42$.

(d) If $xw_1 \notin M(G)$, $w_1\in PD$ and $y\notin PD$, then $|V(H'_{xy})\cap PD|\leq 42$.

Proof. (a) By Lemma 3 and Eq (2.3),

We consider that $\{w_1, z_1\}\cap PD\neq \emptyset$, $|T_4\cap PD|\geq3$ and $|T_3\cap PD|\geq3$, otherwise, $|V(H'_{xy})\cap PD|\leq 43$. Then, w.l.o.g. we assume that $w_1\in PD$.

If $|T_4\cap PD| = 4$, $\{tt_1, t_2t_3\}\subseteq M$ or $\{t_1t_2, t_3t_4\}\subseteq M$.

If $\{tt_1, t_2t_3\}\subseteq M$, $Pr(t)\neq \emptyset$ or $N(t)\cap PD = \{t_1\}$. If $Pr(t)\neq \emptyset$, $u\in Pr(t)$. By Lemma 3 (m), $|V(H'_{xy})\cap PD|\leq 43$. If $N(t)\cap PD = \{t_1\}$, we have $u, w_1\notin PD$, $|T_1\cap PD|\leq 21$ by Lemma 3 (l). Then we obtain $z\in PD$, otherwise, $|V(H'_{xy})\cap PD|\leq 43$ by Lemma 3 (k) and Eq (2.3). If $|T_3\cap PD| = 4$, we have $v\notin PD$, therefore, $|V(H'_{xy})\cap PD|\leq 43$ by Eq (2.3). If $|T_3\cap PD| = 3$, $|V(H'_{xy})\cap PD|\leq 43$ by Eq (2.3).

If $\{t_1t_2, t_3t_4\}\subseteq M$, $\{w, u\}\cap PD = \emptyset$. By Lemma 3 (l), $|T_1\cap PD|\leq 21$, and $v\in PD$. If $z\notin PD$, $|V(H'_{xy})\cap PD|\leq 43$ by Lemma 3 (k) and Eq (2.3). If $z\in PD$, $|T_3\cap PD|\leq 3$ by Lemma 3 (c). Therefore, $|V(H'_{xy})\cap PD|\leq 43$ by Eq (2.3).

If $|T_4\cap PD| = 3$, we consider $|T_1\cap PD| = 22$, and $\{u, v, z_1\}\in PD$. We have $|T_3\cap PD|\neq 4$ by Lemma 3 (c). Therefore, $|V(H'_{xy})\cap PD|\leq 43$ by Eq (2.3).

(b)–(d) Since $|V(H'_{xy})\cap PD|\leq 43$, and, $|V(H'_{xy})\cap PD|$ is even in those cases, so $|V(H'_{xy})\cap PD|\leq 42$.

Lemma 5. Let $PD$ be a minimal paired dominating set of $G'$, $M$ be a perfect matching of $G'[PD]$.

(a) If $\{x, w_1, y, z_1\}\subset PD$, $xw_1\in M(G)$ and $yz_1\notin M$, we have $|V(H'_{xy})\cap PD|\leq 41$.

(b) If $\{x, y\}\cap PD = \emptyset$, $|V(H'_{xy})\cap PD|\leq 40$.

Proof. (a) In this case, we have $z\in PD$ and $zz_1\in M$.

Since $|V(H'_{xy})\cap PD|$ is odd, it's sufficient to show $|V(H'_{xy})\cap PD|\leq 42$. We only consider $\{u, v\}\cap PD\neq \emptyset$ by Lemma 3 (m).

Case 1. $|T_4\cap PD| = 4$.

In this case, we have $\{t_1t_2, t_3t_4\}\subseteq M$ or $\{tt_1, t_2t_3\}\subseteq M$. If $\{t_1t_2, t_3t_4\}\subseteq M$ (or $\{tt_1, t_2t_3\}\subseteq M$), we obtain $u, w \notin PD$, $v\in PD$. Since $z, v\in PD$, $|T_3\cap PD|\leq 3$ by Lemma 3 (c). If $|T_3\cap PD| = 2$, $|V(H'_{xy})\cap PD|\leq 42$ by Eq (2.3). If $|T_3\cap PD| = 3$, $hv\in M$. Thus, $\{q, q_1, d_3\}\cap PD = \emptyset$, otherwise, let $PD' = PD\setminus\{z, z_1\}$, $M' = M\setminus\{zz_1\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction. Since $zz_1\in M$, we obtain that $|T_2\cap PD|$ is odd. So $|T_1\cap PD|\leq 12$. Therefore, $|V(H'_{xy})\cap PD|\leq 42$ by Eq (2.3), see Figure 3 (a).

Case 2. $|T_4\cap PD| = 3$.

If $tw\in M$, $u\notin PD$ or $\{p, p_1, d\}\cap PD = \emptyset$. Otherwise, let $PD' = PD\setminus\{t, w\}$, $M' = M\setminus\{tw\}$. Then, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction. If $\{p, p_1, d\}\cap PD = \emptyset$, $|S_d\cap PD|\leq 3$. W have $|S_d\cap PD| = 3$, $d_3q\in M$, otherwise, $|V(H'_{xy})\cap PD|\leq 42$ by Eq (2.3). Thus $|S_q\cap PD|\leq 3$ by Lemma 3 (j) and Eq (2.3), and $|V(H'_{xy})\cap PD|\leq 42$. If $u\notin PD$, $v\in PD$. Thus, $|T_3\cap PD|\leq 3$ by Lemma 3 (c) and Eq (2.3), and $|V(H'_{xy})\cap PD|\leq 42$.

If $tu\in M$, $|T_3\cap PD|\leq 3$ by Lemma 3 (c). We have $|T_3\cap PD| = 3$, $hv\in M$, otherwise, $|V(H'_{xy})\cap PD|\leq 42$ by Eq (2.3). Let $PD' = PD\setminus\{t, h\}$, $M' = M\setminus\{tu, hv\}\cup \{uv\}$. Therefore, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction.

Case 3. $|T_4\cap PD| = 2$.

Now we only consider $|T_1\cap PD| = 22$, and $\{u, v\}\subset PD$. By Lemma 3 (c) and Eq (2.3), $|V(H'_{xy})\cap PD|\leq 42$.

(b) Since $|V(H'_{xy})\cap PD|$ is even, it's sufficient to show $|V(H'_{xy})\cap PD|\leq 41$.

Case 1. $|\{z_1, w_1\}\cap PD| = 0$.

We obtain $\{z, w\}\subseteq PD$, $|T_2\cap PD|\leq 12$ by Lemma 3 (k). If $|T_4\cap PD|\leq 3$, $|V(H'_{xy})\cap PD|\leq 41$ by Eq (2.3), see Figure 3 (b). If $|T_4\cap PD| = 4$, $t\in PD$ and $Pr(t)\neq \emptyset$ by Lemma 3(d). So, $\{u, v, u_1\}\cap PD = \emptyset$. By Lemma 3 (m) and Eq (2.3), $|V(H'_{xy})\cap PD|\leq 40$.

Case 2. $|\{z_1, w_1\}\cap PD| = 1$.

W.l.o.g. we assume $w_1\in PD$. Thus, $ww_1\in M$, $z\in PD$, $|T_2\cap PD|\leq 12$ by Lemma 3 (k). If $|T_4\cap PD| = 2$, $|V(H'_{xy})\cap PD|\leq 41$ by Eq (2.3). If $|T_4\cap PD| = 4$, we obtain $Pr(t) = \{u\}$ for $t\in PD$, $\{u, u_1, v\}\cap PD = \emptyset$. By Lemma 3 (m) and Eq (2.3), $|V(H'_{xy})\cap PD|\leq 40$. If $|T_4\cap PD| = 3$, $tu\in M$. And $v\in PD$, otherwise $|T_1\cap PD|\leq 21$ by Lemma 3 (l), $|V(H'_{xy})\cap PD|\leq 41$ by Eq (2.3). Thus, $|T_4\cap PD|\neq 4$ by Lemma 3 (d). Afterwards, $|V(H'_{xy})\cap PD|\leq 41$ by Eq (2.3).

Case 3. $|\{z_1, w_1\}\cap PD| = 2$.

Thus, $ww_1\in M$, $zz_1\in M$, $|T_2\cap PD|\leq 12$ by Lemma 3 (k).

If $|T_4\cap PD| = 4$, $t\in PD$ and $\{u, u_1, v\}\cap PD = \emptyset$. By Lemma 3 (m) and Eq (2.3), we have $|V(H'_{xy})\cap PD|\leq 40$.

If $|T_4\cap PD| = 3$, we have $tu\in M$, and $|T_3\cap PD|\leq 3$ by Lemma 3 (c). If $|T_3\cap PD| = 2$, $|V(H'_{xy})\cap PD|\leq 41$ by Eq (2.3). If $|T_3\cap PD| = 3$, $hv \in M$. Let $PD' = PD\setminus\{t, h\}$, $M' = M\setminus\{tu, hv\}\cup \{uv\}$. Therefore, $PD'$ is a paired dominating set and $PD$ is not a minimal paired dominating set, a contradiction.

If $|T_4\cap PD| = 2$, we only consider $|T_1\cap PD| = 22$. Thus, $u, v\in PD$. By Lemma 3 (c), $|T_3\cap PD|\leq 3$. Therefore, $|V(H'_{xy})\cap PD|\leq 41$ by Eq (2.3).

Corollary 6. Let $PD$ be a minimal paired dominating set of $G'$. If $|V(H_{uv}')\cap PD| = 43$ if and only if $|\{u, v\}\cap PD| = 1$, and, $u$ or $v$ is $H_{uv}^I$.

Lemma 7. If $VC_1$ is a minimal vertex cover of $G$, there exists a minimal paired dominating set $PD_1$ of $G'$ with $|PD_1| = 42m+2|VC|$.

Proof. A minimal paired dominating set $PD_1$ can be constructed by the following manner:

For each vertex $x\in VC_1$, we have $|N(x)\cap VC_1| < d(x)\leq3$. So there exists at least one edge $xx_1$ with $x_1\notin VC_1$ in $G$, and maybe exist edges $xx_2$ or $xx_3$.

Therefore, for the edge $xx_1$, put $i$ into $PD'$ for $i\in \{x, w_1,$ $p_2, p_3, p_4, p_5,$ $d, d_1, d_2, d_3,$ $q_2, q_3, q_4, q_5,$ $z, z_1,$ $h, h_2, h_3,$ $v,$ $b_1, b_2, b_3, b_4,$ $s_2, s_3, s_4, s_5,$ $c, c_1, c_2, c_3,$ $r_2, r_3, r_4, r_5,$ $a, a_1, a_2, a_3,$ $t_1, t_2, t_3, t_4\}.$ Put $j$ into $M$ for $j\in\{xw_1,$ $p_5p_4, p_3p_2, dd_1, d_2d_3,$ $q_2q_3, q_4q_5,$ $zz_1,$ $hv,$ $h_2h_3,$ $b_1b_2, b_3b_4,$ $s_2s_3, s_4s_5,$ $cc_1, c_2c_3,$ $r_2r_3, r_4r_5,$ $aa_1, a_2a_3,$ $t_1t_2, t_3t_4\}.$ See Figure 4 (a).

For edges $xx_2, xx_3$, put $i$ into $PD'$ for $i\in \{x,$ $p_2, p_3, p_4, p_5,$ $d, d_1, d_2, d_3,$ $q_2, q_3, q_4, q_5,$ $z, z_1,$ $u, v,$ $h_2, h_3,$ $b_1, b_2, b_3, b_4,$ $s_2, s_3, s_4, s_5,$ $c, c_1, c_2, c_3,$ $r_2, r_3, r_4, r_5,$ $a_1, a_2, a_3, a_4,$ $t_1, t_2, t_3, t_4\}.$ Put $j$ into $M$ for $j\in\{$ $p_5p_4, p_3p_2, dd_1, d_2d_3,$ $q_2q_3, q_4q_5,$ $zz_1,$ $h_2h_3,$ $uv,$ $b_1b_2, b_3b_4,$ $s_2s_3, s_4s_5,$ $cc_1, c_2c_3,$ $r_2r_3, r_4r_5,$ $a_1a_2, a_3a_4,$ $tt_1, t_2t_3\}.$ See Figure 4 (b).

Let $PD_1 = PD'\cup VC_1$. Since vertex $x$ is $M$-saturated in $PD_1$. Therefore, $PD_1$ is a paired dominating set of $G'$.

Since $N(w)\cap PD_1 = \{w_1\}$, then $PD_1\setminus\{w_1\}$ is not a dominating set of $G'$. So $PD_1$ is a minimal paired dominating set of $G'$. And $|PD_1| = |VC_1|+ |VC_1|\times 43 + (m-|VC_1|)\times 42$. Therefore, $|PD_1| = 2|VC_1|+ 42m.$

Let $PD$ be a minimal paired dominating set of $G'$. Algorithm 1 is to obtain a minimal vertex cover $VC$ of $G$, and it terminates in polynomial time.

Lemma 8. If $PD$ is a minimal paired dominating set of $G'$ and $VC$ is a minimal vertex cover of $G$ obtained by Algorithm 1, $|VC|\geq |PD|-42m- |VC|$.

Proof. Let $M$ be the perfect matching of $G[PD]$, $m_e = V(H_{xy}')\cap PD$ where $e = xy\in E(G)$, $M_e = \bigcup_{e\in E(G)}m_e$, $Le = V(G)\setminus (Mo\cup In \cup De)$.

In Algorithm 1, we have:

Claim 9. (a) If $v$ is put into $Mo$ by the while loop (lines 11 to 13) or $De$ (line 18), $v$ will not be put into $In$ later.

(b) For every vertex $v\in V(G)$, $v$ will be put into $Mo$ (or $De$ or $In$) at most once.

(c) $Mo\cap De = \emptyset$, $Mo\cap In = \emptyset$.

(d) If $v\in De$, there exists a vertex $w\in N(v)\cap In$.

(e) If vertex $v\in De\cap In$, we have $v\notin VC'$, that is, $v$ is put into $In$ at first and then into $De$.

(f) If $u, v\in De\cup Mo$, $N(v)\cap N(u)\cap Mo \cap De = \emptyset$.

(g) If $v\in De\setminus In$, there exists a vertex $u\in N(v)\cap (In\setminus De)$, $u\notin VC'$. And $|N(u)\cap De|\leq 2$. What's more, there exists a vertex $w\in N(u) \setminus VC'$. If $w\in In\setminus De$, $|(N(u)\cup N(w))\cap (De\setminus In) |\leq 3$.

Proof. (a) After $v$ is put into $De$ (or $Mo$), every $w\in N(v)$ has a neighbor $v$ which does not belong to $VC$, so $w$ will not be put into $De$. Therefore, $v$ will not be put into $In$ later.

(b)–(d) By (a), it is immediate.

(e) By (a) and (c), it is immediate.

(f) Suppose $v$ is put into $De\cup Mo$. By (a), $w\in N(v)$ will not be put into $De\cup Mo$.

(g) For vertex $v\in De\setminus In$, by (d) and (f), let $u\in N(v)\cap (In\setminus De)$, and $u\notin VC'$, $|N(u)\cap De|\leq 2$.

Since $u\in In\setminus De$, there exists a vertex $w\in N(u) \setminus VC'$.

Since $1\leq |N(u)\cap (De\setminus In) |\leq 2$, $|N(w)\cap (De\setminus In) |\leq 2$. If $w\in In\setminus De$, we may assume $u$ is put into $In$ at first. Then $N(u)\cap (De\setminus In) |\leq 1$, otherwise, $w$ will not be put into $In$ later. Therefore, $|(N(u)\cup N(w))\cap (De\setminus In) |\leq 3$.

Thus,

To show that $|M_e|+|Mo|+|De|-|In| \leq 42m+|VC|$, we use the following strategy.

Discharging procedure:

In the graph $G'$, we set the initial charge of every vertex $v$ to be $s(v) = 1$ for $v\in Mo \cup M_e\cup (De\setminus In)$, $s(v) = -1$ for $v\in In \setminus De$, $s(v) = 0$ otherwise, $s(H_{uv}') = \sum_{x\in V(H_{uv}')}s(x)$, $s(G') = \sum_{v\in V(G')}s(v)$.

Obviously,

We use the discharging procedure, leading to a final charge $s'$, defined by applying the following rules:

Rule 1: For the vertex $v\in Mo$, $v$ is $M$-saturated. Therefore, $v$ is $H_{uv}^I$ for $u$. If $u$ is $H_{uv}^I$, $s(v)$ transmits 1 charge to $s(u)$. If $u$ is $H_{uv}^O$, $s(v)$ transmits 1 charge to $s(H_{uv}')$ which is $[I, O]$.

Rule 2: For each $s(H_{uv}') = 43$, by Corollary 6, $s(H_{uv}')$ transmits 1 charge to $u\in VC'$.

Rule 3: For the vertex $v\in De\setminus In$, by Claim 9 (g), there exists a vertex $u\in N(v)\cap (In\setminus De)$, and a vertex $w\in N(u) \setminus VC'$ and $|N(u)\cap De|\leq 2$. If $|N(u)\cap De| = 2$, $s(v)$ transmits 1 charge to $s(u)$ and transmits 1 charge to $s(H_{uw}')$ which is $[0, 0]$. If $|N(u)\cap De| = 1$, $s(v)$ transmits 2 charge to $s(u)$.

After discharging, we have:

Claim 10. (a) $s'(v)\leq 0$ for $v\in Mo\cup (De \setminus In) \cup (Le\setminus VC) \cup (In\cap De)$.

(b) For each $H_{xy}'$, $s'(H_{xy}')\leq 42$.

(c) $s'(v)\leq 1$ for $v\in (In \setminus De)\cup (Le\cap VC)$.

Proof. (a) If $v\in Mo$, by Claim 9 (f), $v$ will not receive any charge by Rules 1 and 3. Since $N[v]\cap VC' = N[v]$. By Lemmas 4 and 5, $v$ will not receive any charge by Rule 2. Therefore, $s'(v) = 0$.

If $v\in De \setminus In$, $v\in VC'$. By Claim 9 (f), $N(v)\cap Mo = \emptyset$. Thus, $v$ will not receive any charge by Rules 1 and 3. Since $v$ is $H_{uv}^I$ for $u$. By Lemmas 4 and 5, if $u\in VC'$, $v$ will not receive any charge by Rule 2. If $u\notin VC'$, $v$ will receive 1 charge at most by Rule 2. Afterwards, by Rule 3, $v$ will transmit 2 charge to others, so $s'(v)\leq 0$.

If $v\in Le\setminus VC$, $v$ will not receive any charge by Rules 1, 2 and 3.

If $v\in In\cap De$, $v\notin VC'$ by Claim 9 (e). Thus, $v$ will not receive any charge by Rules 1 and 2. By Claim 9 (f), $v\in De$, $N(v)\cap De = \emptyset$. Thus, $v$ will not receive any charge by Rule 3.

(b) If $H_{uw}'$ is $[I, I]$ or $[O, O]$ or $[I, 0]$ or $[O, 0]$, $s(H_{uw}')$ will not receive any charge by Rules 1, 2 and 3. If $H_{uw}'$ is $[0, 0]$, $s(H_{uw}')$ will not receive any charge by Rules 1 and 2.

If $H_{uw}'$ is $[0, 0]$, by Claim 9 (g), $|(N(u)\cup N(w))\cap (De\setminus In) |\leq 3$. Thus, $s(H_{uw}')$ will receive 2 charge at most from $s(x)$ where $x\in N(v)\setminus \{w\}$ by Rule 3.

And if $s(H_{uw}') = 43$, by Corollary 6, there exists a vertex $u\in VC'$ and $u$ is $H_{uw}^I$. Therefore, $s'(H_{uw}') = 42$ by Rule 2.

Thus, by Lemmas 4 and 5, $s'(H_{uw}')\leq 42$.

(c) If $v\in In\setminus De$, $v\notin VC'$, $v$ will receive any charge by Rules 1 and 2. And there exists a vertex $w\in N(v)$ $w\notin VC'$ and $w\notin De\setminus In$. So $v$ will receive 2 charge at most by Rule 3, $s'(v)\leq -1+2 = 1$.

If $v\in Le\cap VC$, $v$ will receive any charge by Rule 3. By Lemmas 4, 5 and Corollary 6, $H_{uv}'$ is $[I, 0]$ if $s(H_{uv}') = 43$. Since $v$ can be $M$-saturated once, $v$ will receive 1 charge at most by Rules 1 and 2. Thus, $s'(v)\leq 0+1 = 1$.

By Claim 10,

Thus, by Eq (2.4),

Let $PD^*$ be a $\Gamma_{pr}(G')$-set of $G'$, and be the Input of Algorithm 1. Then we obtain the Output $VC$ by Algorithm 1.

Since

By Lemma 8,

Let $VC^*$ be a $VC$-set of $G$. Since $|VC|\leq |VC^*|$,

By Lemma 7, $|PD^*|\geq |PD_1| = 42m+2|VC^*|$. By Lemma 8,

Thus,

Therefore, by Eq (2.6) and Eq (2.7), $f$ is an $L$-reduction with $\alpha = 128$, $\beta = 1$.

3.   Conclusions

$Upper$-$PDS$ for bipartite graphs is proved to be APX-complete with maximum degree 4 and still open with maximum degree 3. In this paper, we show that $Upper$-$PDS$ for bipartite graphs with maximum degree 3 is APX-complete by providing an $L$-reduction $f$ from $MAX$-$MIN$-$VC$ for bipartite graphs to it.

Acknowledgments

This work was supported by the National Key R & D Program of China (No. 2018YFB1005100), the Guangzhou Academician and Expert Workstation (No. 20200115-9) and the Innovation Ability Training Program for Doctoral student of Guangzhou University (No. 2019GDJC-D01).

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.