In this post, we will prove that the set-partition problem is NP-complete using a reduction from the subset sum problem (which is NP-complete). This is Exercise 34.5-5 in CLRS3. We will follow the template given in an earlier post.
Given a set of numbers, determine whether can be partitioned into and , such that:
Showing the problem is in NP
Let be the certificate. We can verify the certificate in linear time by summing the elements in each set, and comparing it
Showing the problem is NP-hard
We will show that the set-partition problem is NP-hard by showing:
We will prove that the existence of with sum can be partitioned into as described by the set-partition problem ( being the sum of ). We note that can be constructed in by first summing the elements in and then adding to S, which proves our reduction is performed in polynomial time.
We will now prove both directions of the biconditional separately.
the set-partition problem on has a solution
Suppose exists. Let be , i.e the “out”-elements. Let be the sum of . Let and be the sum of . We can now make the following observations:
The set-partition problem on has a solution
Suppose an equal-sum partitioning of exists. The sum of each partition must then be . We consider the partition containing the element to be . Let . We can observe . The sum of is . In other words: is a subset of with sum , i.e. a witness to
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009.