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[1]). This is Exercise 34.5-5 in CLRS3[1]. 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:

(1) $\begin{equation*}\sum_{x \in A} x = \sum_{x \in \overline{A}} x\end{equation*}$

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 it

Showing the problem is NP-hard

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

(2) $\begin{equation*}\textsc{Subset-Sum} \leq_\text{P} \textsc{Set-Partition}\end{equation*}$

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:

(3) $\begin{align*}o &= s - t\\o - t &= s - 2t \qquad &\text{Difference in sum between the \textit{O} and \textit{T}}\\t' &= t + (s - 2t)\\ &= s - t \qquad &\text{the sums of \textit{T'} and \textit{O} are equal}\\ &= o\end{align*}$

This proves:

(4) $\begin{equation*}\exists T \implies (T', O)~\text{is a solution to the set-partition problem on}~ S'\end{equation*}$

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$