[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

The SUBSET SUM problem is defined by the language

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) bi + 1, where Δ(i) is the set of edges that have v as an endpoint. For each edge i, include bi. Let the target sum k' = ∑i in E bi + 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.


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.


2014-06-17 11:58