The SUBSET SUM problem is defined by the language

• { (S,k) : S is a set of integers that has a subset S' with ∑S' = k }.

We can show that SUBSET SUM is NP-hard by reduction from INDEPENDENT SET (see PvsNp for definitions of these terms).

Start with the graph G and the desired size of the independent set k. Choose a base b that is larger than |V| (to avoid carries in the sum); we will represent our numbers in base b. Number the edges from 1 to m.

For each vertex v, include in S the number ∑_{i in Δ(i)} bⁱ + 1, where Δ(i) is the set of edges that have v as an endpoint. For each edge i, include bⁱ. Let the target sum k' = ∑_{i in E} bⁱ + k.

Example: let G have edges ab, ac, ad, bc, and cd and suppose k = 2. Then the set consists of the nine numbers (read across rows):

Edge:   ab ac ad bc cd -

a       1  1  1  0  0  1
b       1  0  0  1  0  1
c       0  1  0  1  1  1
d       0  0  1  0  1  1

ab      1  0  0  0  0  0
ac      0  1  0  0  0  0
ad      0  0  1  0  0  0
bc      0  0  0  1  0  0
bd      0  0  0  0  1  0

k'      1  1  1  1  1  2

How can we construct the target? We need to take exactly k vertices to get a k in the last digit of the sum. We can't take more than one vertex per edge, or we'll get a 2 in one of the earlier digits---this means that whatever vertices we do take form an independent set, and thus if we do get k' then an independent set of size k exists.

Conversely, summing up an independent set fills it some (but generally not all) of the digits except the end; the numbers corresponding to each edge let us fill in the gaps, showing that if an independent set of size k exists we can construct k'.

For example, in the case above we sum

  b  100101
+ d  001011
+ ac 010000

= k' 111112

and get k' from the independent set {b, d}.

Since we've shown that k' can be made as a sum of elements in S if and only if G has an independent set of size k, and since the construction is easily seen to be polynomial, we have a poly-time reduction from INDEPENDENT SET to SUBSET SUM, which shows that SUBSET SUM is NP-hard. It's also in NP (guess the correct subset and verify it in poly time), so it's NP-complete.

1. PARTITION

An even simpler version of SUBSET SUM is PARTITION, which asks if there is a subset of S with total value ½∑_{x in S} x. It's easy to reduce PARTITION to SUBSET SUM (set k = ½∑_{x in S} x), but this doesn't tell us much about PARTITION; instead we want a reduction in the other direction. The basic trick is to add a new element y to S so that any even split of S ∪ {y} contains a subset that has total weight k without containing y or that has total weight k+y and contains y. The details are left as an exercise.

CategoryAlgorithmNotes