Proving set-partition problem is NP-complete (using reduction from subset sum)

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 also happens to be Exercise 34.5-5 in CLRS3.

We will follow the template given in an earlier post.

Problem statement

Given a set SS of numbers, determine whether SS can be partitioned into AA and A‾=S−A\overline{A} = S - A, such that: ∑x∈Ax=∑x∈A‾x \sum_{x \in A} x = \sum_{x \in \overline{A}} x

Showing the problem is in NP

Let (A,A‾)(A, \overline{A}) be the certificate. We can verify the certificate in linear time by summing the elements in each set, and comparing the result.

Showing the problem is NP-hard

We will show that the set-partition problem is NP-hard by showing:

Subset-Sum≤PSet-Partition \text{Subset-Sum} \leq_\text{P} \text{Set-Partition}

Reduction

We will prove that the existence of T⊆ST \subseteq S with sum t  ⟺  S′=S∪{s−2t}t \iff S' = S \cup \{s - 2t\} can be partitioned into (A,A‾)(A, \overline{A}) as described by the set-partition problem (ss being the sum of SS). We note that S′S' can be constructed in O(∣S∣)\mathcal{O}(|S|) by first summing the elements in SS and then adding {s−2t}\{s - 2t\} to S, which proves our reduction is performed in polynomial time.

We will now prove both directions of the biconditional separately.

∃T  ⟹  \exists T \implies the set-partition problem on S′S' has a solution

Suppose TT exists. Let OO be S−TS - T, i.e the “out”-elements. Let oo be the sum of OO. Let T′=T∪s−2tT' = T \cup {s - 2t} and t′t' be the sum of T′T'. We can now make the following observations:

o=s−to−t=s−2tDifference in sum between the O and Tt′=t+(s−2t)=s−tthe sums of T′ and O are equal=o \begin{aligned} o &= s - t\\ o - t &= s - 2t \qquad &\text{Difference in sum between the}~O~\text{and}~T\\ t' &= t + (s - 2t)\\ &= s - t \qquad &\text{the sums of}~T'~\text{and}~O~\text{are equal}\\ &= o \end{aligned} This proves: ∃T  ⟹  (T′,O) is a solution to the set-partition problem on S′ \exists T \implies (T', O)~\text{is a solution to the set-partition problem on}~ S'

The set-partition problem on S′S' has a solution   ⟹  ∃T\implies \exists T

Suppose an equal-sum partitioning (A′,A′‾)(A', \overline{A'}) of S′=S∪{s−2t}S' = S \cup \{s - 2t\} exists. The sum aa of each partition must then be s+(s−2t)2=s−t\frac{s + (s -2t)}{2} = s - t. We consider the partition containing the element {s−2t}\{s - 2t\} to be A′A'. Let A=A′−{s−2t}A = A' - \{s - 2t\}. We can observe S′−S={s−2t}  ⟹  A⊆SS' - S = \{s - 2t\} \implies A \subseteq S. The sum of AA is s−t−(s−2t)=ts - t - (s - 2t) = t. In other words: AA is a subset of SS with sum tt, i.e. a witness to ∃T ■\exists T~\blacksquare