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

  1. [1]
    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009.

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.