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 \(S\) of numbers, determine whether \(S\) can be partitioned into \(A\) and \(\overline{A} = S - A\), such that: \[ \sum_{x \in A} x = \sum_{x \in \overline{A}} x \]
Showing the problem is in NP
Let \((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:
\[ \text{Subset-Sum} \leq_\text{P} \text{Set-Partition} \]
Reduction
We will prove that the existence of \(T \subseteq S\) with sum \(t \iff S' = S \cup \{s - 2t\}\) can be partitioned into \((A, \overline{A})\) as described by the set-partition problem (\(s\) being the sum of \(S\)). We note that \(S'\) can be constructed in \(\mathcal{O}(|S|)\) by first summing the elements in \(S\) and then adding \(\{s - 2t\}\) to S, which proves our reduction is performed in polynomial time.
We will now prove both directions of the biconditional separately.
\(\exists T \implies\) the set-partition problem on \(S'\) has a solution
Suppose \(T\) exists. Let \(O\) be \(S - T\), i.e the “out”-elements. Let \(o\) be the sum of \(O\). Let \(T' = T \cup {s - 2t}\) and \(t'\) be the sum of \(T'\). We can now make the following observations:
\[ \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: \[ \exists T \implies (T', O)~\text{is a solution to the set-partition problem on}~ S' \]
The set-partition problem on \(S'\) has a solution \(\implies \exists T\)
Suppose an equal-sum partitioning \((A', \overline{A'})\) of \(S' = S \cup \{s - 2t\}\) exists. The sum \(a\) of each partition must then be \(\frac{s + (s -2t)}{2} = s - t\). We consider the partition containing the element \(\{s - 2t\}\) to be \(A'\). Let \(A = A' - \{s - 2t\}\). We can observe \(S' - S = \{s - 2t\} \implies A \subseteq S\). The sum of \(A\) is \(s - t - (s - 2t) = t\). In other words: \(A\) is a subset of \(S\) with sum \(t\), i.e. a witness to \(\exists T~\blacksquare\)