Gholam Hassan Shirdel^a , Nasrin Kahkeshani^a

^aDepartment of Mathematics, Faculty of Basic Sciences, University of Qom, Qom, I. R. Iran

g.h.shirdel@qom.ac.ir, nasrinkahkeshani@yahoo.com

The purpose of the independent set interdiction problem in the weighted graph G is to determine a set of vertices R^∗ such that the weight of the maximum independent set in G − R^∗ is minimized. We define an approximate solution for this problem. Then, an upper bound for the relative error of this problem is obtained. We show that the limit of the relative error of the independent set interdiction problem in some subclasses of the generalized Petersen graphs is zero as the number of vertices tends to infinity.

Keywords: independent set, interdiction, generalized Petersen graph

Mathematics Subject Classification : 05C69

DOI: 10.5614/ejgta.2015.3.2.2

1. Introduction

Two different forces, the follower and interdictor, compete in the interdiction problems. The follower tries to optimize the objective of problem, but the interdictor attempts to limit the follower's action. In other words, the interdictor wants to change the optimal value of problem. The interdictor does this act by deleting the vertices or edges of the problem. The interdiction problem has discussed on some basic problems such as the maximum flow network, shortest path and so on [2, 4]. This problem has received some attention in recent years and has expressed on the problems of graph theory such as the vertex cover, independent set, connectivity, matching and so on [1, 5, 6]. Shen et al. [5] introduced an interdiction problem that disconnectivity of a graph is maximized by deleting a subset of vertices. The connectivity of graph is measured by three metrics. This problem with three metrics can be formulated as a linear programming problem. Zenklusen

Received: 16 November 2014, Revised: 17 March 2015, Accepted: 24 March 2015.

[6] considered the matching interdiction problem by removing the vertices and edges of a graph. Consider a graph G that each edge has a positive weight. The purpose of this problem is to find a subset of vertices (edges) such that the weight of the maximum matching in G without these vertices (edges) is minimized and the deletion cost of these vertices (edges) does not exceed the interdiction budget. Zenkluen [6] considered the complexity of this problem on some graphs. He introduced an approximate solution for this problem. Also, an algorithm for the matching interdiction problem on graphs with bounded treewidth was presented. The independent set interdiction problem is a combinatorial optimization problem that was introduced by Bazgan et al. [1]. This problem is expressed as follows. Consider a graph G where each vertex has a positive weight. The purpose is to find a subset of vertices whose removal from G results in the greatest decrease in the weight of the maximum independent set. Bazgan et al. [1] show that this problem is NP-hard on the bipartite graphs and is polynomial on the unweighted bipartite graphs.

In this paper, we consider the independent set interdiction problem and present an approximate solution for it. Then, an upper bound for the relative error of this problem is obtained. Using the upper bound of the relative error, we can conclude that the approximate and optimal solutions of the independent set interdiction problem in some subclasses of the generalized Petersen graphs are equal when the number of vertices increases.

2. Basic facts

Let G = (V, E) be an undirected graph such that V and E are the sets of vertices and edges, respectively. An independent set of the graph G is a subset of vertices such that no two vertices have a common edge. Suppose

\[\alpha(G) = \max\{|A||A \text{ is an independent set of } G\},\]

where |A| is the cardinality of A. The independent set with cardinality \(\alpha(G)\) is denoted by S and \(\alpha(G)\) is called the independence number of G. Now, consider the graph G with vertex weights \(w:V\to\mathbb{N}\). We define the independence number of the weighted graph G as follows:

\[\alpha_w(G) = \max\{w(A)|A \text{ is an independent set of } G\},\]

where \(w(A) = \sum_{v \in A} w(v)\). The set \(S_w\) with the independence number \(\alpha_w(G)\) is called the maximum independent set of the weighted graph G. For a fixed \(B \in \mathbb{N}\), the independent set interdiction problem is defined as follows:

\[\alpha_w(G - R^*) = \min\{\alpha_w(G - R)|R \subseteq V, |R| = B\}\]

The set \(R^*\) is the solution of the independent set interdiction problem and is called the optimal interdiction set of G. Let \(\{a_1,\ldots,a_k\}\) be the maximum independent set of the weighted graph G such that \(w(a_1) \geq \cdots \geq w(a_k)\). Let \(B \leq k\). We define the set \(R = \{a_1,\ldots,a_B\}\) as the approximate solution of the problem. The relative error of the independent set interdiction problem is defined as follows:

\[\delta_G = \frac{\alpha_w(G - R) - \alpha_w(G - R^*)}{\alpha_w(G - R^*)}\]

In this paper, we use asymptotic notation ∼ which is defined as follows. Let f(n) and g(n) be two positive functions. If limn→∞ f(n) ^g(n) = 1, then f(n) ∼ g(n). It is said that f(n) and g(n) are asymptotically equivalent.

3. Main results

Theorem 3.1. For the weighted graph G, we have:

\[\delta_G \le \frac{\sum_{i=1}^B w(a_i)}{\alpha_w(G) - \sum_{i=1}^B w(a_i)}\] (1)

Proof. The set S − R is an independent set of the graph G − R. Therefore, we have the following relation:

\[\alpha_w(G - R) \ge w(S - R)\] \[= \alpha_w(G) - \sum_{i=1}^{B} w(a_i)\]

It results:

\[\alpha_w(G) - \alpha_w(G - R) \le \sum_{i=1}^B w(a_i)\] (2)

Since the maximum independent set of the graph G − R is an independent set of the graph G and αw(G − R) ≤ αw(G), we have:

\[\alpha_w(G - R) - \alpha_w(G - R^*) \le \alpha_w(G) - \alpha_w(G - R^*) \tag{3}\]

Since the maximum independent set of the graph G − R^∗ is an independent set of the graph G, αw(G−R^∗ ) ≤ αw(G). Notice that αw(G−R)−αw(G−R^∗ ) ≥ 0 and αw(G)−αw(G−R^∗ ) ≥ 0. Let ^{Se = S}\R^∗ . Therefore,

\[\alpha_w(G) - w(\widetilde{S}) \le \sum_{i=1}^B w(a_i) \tag{4}\]

Since the set ^Se is an independent set of the graph ^{G − R∗} , we have the following relation:

\[\alpha_w(G - R^*) \ge w(\widetilde{S}) \tag{5}\]

According to the relations (4) and (5), we obtain the following inequality:

\[\alpha_w(G) - \alpha_w(G - R^*) \le \sum_{i=1}^B w(a_i)\] (6)

By the relations (3) and (6), we have:

\[\alpha_w(G - R) - \alpha_w(G - R^*) \le \sum_{i=1}^B w(a_i)\] (7)

The following relation is derived by the relations (6) and (7):

\[\frac{\alpha_w(G - R) - \alpha_w(G - R^*)}{\alpha_w(G - R^*)} \le \frac{\sum_{i=1}^B w(a_i)}{\alpha_w(G) - \sum_{i=1}^B w(a_i)}\]

This completes the proof.

Definition 3.1. The generalized Petersen graph P(n, k), where 1 ≤ k ≤ [ n−1 2 ] and n ≥ 3, is the graph with vertex set {vⁱ , uⁱ |1 ≤ i ≤ n} and edge set

\[\{(v_i, v_{i+1}), (v_i, u_i), (u_i, u_{i+k}) | 1 \le i \le n\},\\]

where the subscripts are expressed as integers modulo n. This graph has 2n vertices and 3n edges.

Theorem 3.2. There is a function w : V → N such that

• 1. αw(P(n, k) − R) ∼ αw(P(n, k) − R^∗ ) for even n and odd k.
• 2. Let B ≤ n−1 2 and k = 1, 3, 5. Then, αw(P(n, k) − R) ∼ αw(P(n, k) − R^∗ ) for odd n.

Proof. (1) Suppose that n is even and k is odd. Consider the following two independent sets in the graph P(n, k):

\[S_1 = \{u_2, u_4, \dots, u_n, v_1, v_3, \dots, v_{n-1}\}\]
\[S_2 = \{u_1, u_3, \dots, u_{n-1}, v_2, v_4, \dots, v_n\}\]

By [3], we have α(P(n, k)) = n. Then, S = S¹ = S2. Let w(ui) = wⁱ for each 1 ≤ i ≤ n and w(vi) = w2n−i+1 for each 1 ≤ i ≤ n such that w¹ ≤ w² ≤ · · · ≤ wⁿ < wn+1 < · · · < w2n. By the weights of vertices in P(n, k), S^w = S1. The weight of the maximum independent set in the graph P(n, k) is equal to:

\[\alpha_w(P(n,k)) = \sum_{i=1}^n w_{2i} \tag{8}\]

By the relations (1) and (8), we have:

\[\delta_{P(n,k)} \le \frac{\sum_{i=n-B+1}^{n} w_{2i}}{\sum_{i=1}^{n-B} w_{2i}}\] (9)

Let wⁱ = i for each 1 ≤ i ≤ 2n. Using this in (9) yields:

\[\delta_{P(n,k)} \le \frac{\sum_{i=n-B+1}^{n} i}{\sum_{i=1}^{n-B} i}\] \[= \frac{2Bn + (B-B^2)}{n^2 + (1-2B)n + (B^2-B)}\]

If B is constant, then \(\lim_{n\to\infty} \delta_{P(n,k)} = 0\). Therefore,

\[\lim_{n \to \infty} \frac{\alpha_w(P(n,k) - R)}{\alpha_w(P(n,k) - R^*)} = 1\]

(2) Let n be odd and k = 1, 3, 5. By [3], we have:

\[\alpha(P(n,k)) = \begin{cases} n-1 & k=1\\ n-2 & k=3\\ n-3 & k=5 \end{cases}\]

In this case, the set S contains \(\frac{n-1}{2}\) vertices from the set \(\{v_1, v_2, \dots, v_n\}\) and \(\alpha(P(n, k)) - \frac{n-1}{2}\) vertices from the set \(\{u_1, u_2, \dots, u_n\}\). Let

\[w(u_i) = w \quad \forall i, 1 \le i \le n\]

\[w(v_i) = w_i \quad \forall i, 1 \le i \le n\]

such that \(w \leq w_1 < w_2 < \cdots < w_n\). Therefore, \(S_w\) contains the vertices \(v_3, v_5, \ldots, v_n\) and \(\alpha(P(n,k)) - \frac{n-1}{2}\) vertices from the set \(\{u_1, u_2, \ldots, u_n\}\). The weight of the maximum independent set in the graph P(n,k) is equal to:

\[\alpha_w(P(n,k)) = (\alpha(P(n,k)) - \frac{n-1}{2})w + \sum_{i=1}^{(n-1)/2} w_{2i+1}\]

Since \(B \leq \frac{n-1}{2}\), the upper bound of \(\delta_{P(n,k)}\) is obtained as follows:

\[\delta_{P(n,k)} \le \frac{\sum_{i=(n-2B+1)/2}^{(n-1)/2} w_{2i+1}}{\frac{n-k}{2} w + \sum_{i=1}^{(n-2B-1)/2} w_{2i+1}}\](10)

Let \(w_i = i\) for every \(1 \le i \le n\) and w = 1. In this case, the relation (10) is derived as follows:

\[\delta_{P(n,k)} \le \frac{\sum_{i=(n-2B+1)/2}^{(n-1)/2} (2i+1)}{\frac{n-k}{2} + \sum_{i=1}^{(n-2B-1)/2} (2i+1)}\] \[= \frac{4Bn - 4B^2 + 4B}{n^2 + (4-4B)n + 4B^2 - 4B - 2k - 3}\]

If B is constant, then \(\lim_{n\to\infty} \delta_{P(n,k)} = 0\). According to the relation (1), we have:

\[\lim_{n \to \infty} \frac{\alpha_w(P(n,k) - R)}{\alpha_w(P(n,k) - R^*)} = 1\]

The Theorem follows.

By Theorem 3.2, we can conclude that the sets R and \(R^*\) in some subclasses of the generalized Petersen graphs can be equal when n is large.

Acknowledgement

We express our sincere thanks to the referee for his/her comments and helpful remarks.

References

• [1] C. Bazgan, S. Toubaline and Z. Tuza, The most vital nodes with respect to independent set and vertex cover Discrete Appl. Math. 159 (2011), 1933–1946.
• [2] H.W. Corley and H. Chang, Finding the n most vital nodes in a flow network, Management Sci. 21 (1974), 362–364.
• [3] J. Fox, R. Gera and P. Stanic ˘ a, The independence number for the generalized Petersen graphs, ˘ Ars Comb. 103 (2012), 439–451.
• [4] E. Israeli and R.K. Wood, Shortest path network interdiction, Networks 40 (2002), 97–111.
• [5] S. Shen, J.C. Smith and R. Goli, Exact interdiction models and algorithms for disconnecting networks via node deletions Discrete Optim. 9 (2012), 172–188.
• [6] R. Zenklusen, Matching interdiction, Discrete Appl. Math. 158 (2010), 1676–1690.