Reduction of the Independent Set Problem to the Knapsack Problem

We define an instance of the knapsack problem to consist of a number C, and a list of positive numbers X = x_{1}, … x_{p}. The ordered pair (C, X) is a member of the language Knapsack if there is some set of numbers S in the range {1, … p} such that ∑ {x_{i} : i ∈ S} = C.

We first prove that Knapsack is N P, using the certificate method. If (C, X) ∈Knapsack, then the set S itself is a certificate, and verification program is straightforward: simply add the weights.

We define a P-time reduction R of IND to Knapsack, where IND is the independent set problem.

We assume that all of our languages (problems) are over Σ = {0, 1}, the binary alphabet. and each reduction must be a function

R : Σ^{∗} → Σ^{∗}

. When we define R(w) below, we will assume that w is an instance of the independent set problem. If w is any other string, we define R(w) = ε, the empty string. No further discussion of this case is necessary.

Let G = (V, E) be a graph, and k a number. Then ⟨G⟩⟨k⟩ is an instance of the independent set problem. We define R(⟨G⟩⟨k⟩), an instance of the knapsack problem, as follows.

Write V = {v_{1}, … v_{n}} and E = {e_{1}, … e_{m}}, the vertices and edges of G, respectively. We say that v_{i} meets e_{i} if v_{i} is one of the two end points of e_{j}.

We will have two classes of entries in our list X, those derived from vertices of G, and those derived from edges of G. We call these Y = y_{1}, … y_{n} and z_{1} … z_{m}. We will then let p = n + m, and X = Y + Z, the concatenation of the two lists. More formally:

• For any 1 ≤ i ≤ n, let y_{i} = 10^{m+1} + ∑ {10^{j} : v_{i} meets e_{j}}.

• For any 1 ≤ j ≤ m, let z_{j} = 10^{j}

• For any 1 ≤ ℓ ≤ n + m, we define x_{ℓ} = \{ \begin{matrix}y_{ℓ} if ℓ ≤ n \\ z_{n+ℓ} otherwise \end{matrix} Then, let X = x_{1}, … x_{n+m}.

• Let C = k 10^{m+1} + ∑_{j=1}^{m} 10^{j}

By the following two lemmas, R is a reduction of IND to Knapsack.

Lemma 1 If G has an independent set of size k, then (C, X) ∈ Knapsack.

Proof: Suppose I is a set consisting of k vertices of G. Let J be the set of edges which do not meet any of the vertices in I. Define

• Y = {y_{i} : v_{i} ∈ I}

• Z = {z_{j} : e_{j} ∈ J }

• X = Y ∪ Z

We claim that ∑ X = C. We analyze the sum by examining “places,” just like we did in elementary school.

We first examine places 1 through m, namely the coefficients of 10^{j} for each j. If there is some vertex v_{i} that meets e_{j}, y_{i} contributes 1 to that place. Since I has at most one vertex which meets e_{j}, and since e_{j} ∉ J, the coefficient of X in the j^{th} place is 1, just as in C. On the other hand, if there is no vertex that meets e_{j}, then there is no y_{i} which contributes to the j^{th} place of ∑ X, but z_{j} does contribute a 1 in that place. In either case, ∑ X and C agree in the j^{th} place.

Finally, we note that, disregarding those first m places, ∑ X has k copies of 10^{m+1}, as does C, and we are done. □

Example

Let G be the graph illustrated below, where n = 6 and m = 8. Let k = 3. The set I = {v_{1}, v_{3}, v_{6}} is an independent set of vertices of G of size k. In our reduction, J = {e_{4}, e_{7}}. We write k and all the weights in base 10. The first array shows the weights of all items, while the second array shows that the weights of the selected items sum to C

\begin{aligned}C & = & 3 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ y_{1} & = & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ y_{2} & = & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ y_{3} & = & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ y_{4} & = & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ y_{5} & = & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ y_{6} & = & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ z_{1} & = & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ z_{2} & = & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ z_{3} & = & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ z_{4} & = & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ z_{5} & = & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ z_{6} & = & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ z_{7} & = & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ z_{8} & = & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{aligned}  \begin{aligned}x_{1} & = & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ x_{3} & = & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ x_{6} & = & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ y_{4} & = & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ y_{7} & = & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ C & = & 3 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \end{aligned}