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 k.

\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 & 1 & 0 & 1 & 1 & 1 & 0 & 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}