Subset Sum: reduce special to general case

Question

Wikipedia states the subset sum problem as finding a subset of a given multiset of integers, whose sum is zero. Further it states that it is equivalent to finding a subset with sum $s$ for any given $s$.

So I believe as they are equivalent, there must be a reduction in either side. The one from $s$ to zero is trivial by setting $s = 0$. But I had no luck finding a reduction from zero to $s$, i.e. given a set of integers $A$, construct a set of integers $B$ containing a subset with sum $s$ (for any $s$), if and only if there is as subset of $A$ with sum zero.

Can you give me some pointers?

Answer 1

You actually already have a reduction from special to general. By setting $s=0$, you are basically using the general algorithm to solve the special problem.

For the other way round (i.e. a reduction from general to special):

Suppose you are given a set $S = \{x_1, \dots, x_n\}$ and a number $K$ and you have to determine if there is some subset of $S$ which sums to $K$.

Now you want to solve this problem, given an algorithm for the case where you can determine if some subset sums to $0$.

Now if $x_i \gt 0$, we have an easy reduction: $S' = \{x_1, x_2, \dots, x_n, -K\}$.

$S'$ has a subset of sum $0$ iff $S$ has a subset of sum $K$.

The problem occurs when we can have $x_i \le 0$ for some of the $i$.

We can assume that $K \gt 0$ (why?).

Suppose the sum of the positive $x_i$ is $P$ and the negative $x_i$ is $N$.

Now construct a new set $S' = \{y_1, y_2 \dots, y_n\}$ such that

$y_i = x_i + M$ where $M = P + |N| + K$.

Each $y_i \gt 0$.

Now run the zero-subset-sum algorithm on the sets

$ S' \cup \{-(K+M)\}$

$ S' \cup \{-(K+2M)\}$

$ S' \cup \{-(K+3M)\}$

$\dots$

$ S' \cup \{-(K+nM)\}$

It is easy to show that if $S$ has a subset of sum $K$, then at least one of the above sets has subset of sum zero.

I will leave the proof of the other direction to you.

Answer 2

Aryabhata's answer can be fixed up by making use of the fact that we can multiply all the numbers by some large $c$, and then add something small to each one to act like a "presence tag", and then supply some extra numbers that will allow us to get to zero if we could get to $cK$ without them. Specifically, we will use $c=2(n+1)$ and 1 as the presence tag.

Given an instance $(S = \{x_1, \dots, x_n\}, K)$ of the general problem with target value $K$, we will create an instance of the specific problem (with target value 0) that contains:

• $Y = \{y_1, \dots, y_n\}$, where $y_i = 2(n+1)x_i + 1$.
• The number $z = -2K(n+1)-n$.
• $n-1$ copies of the number 1, to be referred to as "pull-up" numbers.

I'll assume as Aryabhatta does that $K$ is positive. (Since it's been 6 years, I'll answer his exercise for the reader: the reason we can do this is that if we swap the signs of all numbers in an instance of the general problem, including $K$, then we wind up with a new, equivalent problem instance. That means that an algorithm to solve positive-$K$ instances suffices to solve any problem -- to solve an instance with negative $K$, we could perform this sign-swap, run that algorithm, and forward its answer on as the answer to the original question. And of course if $K=0$ then we don't need to perform any transformation of the general case into the special case at all!)

First let's show that a YES answer to the given instance of the general problem implies a YES answer to the constructed instance of the special problem. Here we can assume that some solution $\{x_{j_1}, \dots, x_{j_m}\}$ to the general problem exists: that is, this nonempty collection of $m$ numbers sums to $K$. So if we take the corresponding $y$-values $\{y_{j_1}, \dots, y_{j_m}\}$ into our solution to the constructed instance, they will sum to $2K(n+1)+m$. We can then choose to include $-2K(n+1)-n$ in the solution, leaving us with a sum of $m-n$. Since $1 \le m \le n$, this in the range $[-n+1, 0]$, which we can successfully pull up to 0 by including some subset of the pull-up numbers.

Now let's show that a YES answer to the constructed instance implies a YES answer to the original given instance. This is where the multiplication by $2(n+1)$ becomes important -- it is what allows us to be certain that the extra numbers we included can't "do too much".

Here we may assume that some solution $\{y_{j'_1}, \dots, y_{j'_{m'}}\}$ to the constructed instance exists: that is, this nonempty collection of $m'$ numbers sums to 0. By the problem requirements, this solution contains at least one element. Further, it must contain at least one element from $Y$, since without this it is impossible to reach a total of 0: If only pull-up numbers are present, then the sum is necessarily in the range $[1, n-1]$ (note that in this case at least one pull-up number must be present, and all of them are strictly positive, so the sum cannot be 0); while if the solution consists of just $z$ and some pull-up numbers, then the total is necessarily negative because $z = -2K(n+1)-n \le -n$ and the most that the pull-up numbers can increase the sum by is $n-1$.

Now suppose towards contradiction that the solution does not contain $z$. Every element in $Y$ consists of two terms: A multiple of $2(n+1)$, and a +1 "presence tag". Notice that the +1 term on each of the $n$ elements of $Y$ increases the sum by 1 if that element is chosen, as does each of the up to $n-1$ pull-up numbers that are chosen, so the total contributed by these 2 sources to any solution is at least 1 (because we established in the previous paragraph that at least one element of $Y$ must be chosen) and at most $n + n-1 = 2n-1$. In particular, this implies that the sum of these two sets of terms, when taken modulo $2(n+1)$, is nonzero. Under the assumption that the solution does not contain $z$, the only other components in this sum are the multiples of $2(n+1)$ contributed by the chosen members of $Y$, which do not affect the value of the sum when taken modulo $2(n+1)$. Thus the sum of all terms in the solution, when taken modulo $2(n+1)$, is nonzero, meaning it cannot be equal to the target sum of 0, meaning it cannot be a valid solution at all: we have found a contradiction, meaning that it must be that $z = -2K(n+1)-n$ is present in every solution after all.

So every solution contains $z$. We know that

$(-2K(n+1) - n) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}} + 1) + \sum {\text{pull-ups}} = 0$,

and we can rearrange the terms:

$-2K(n+1) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}}) - (n + \sum_{i'=1}^{m'} 1 + \sum {\text{pull-ups}}) = 0$

$-2K(n+1) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}}) - (n + m' + \sum {\text{pull-ups}}) = 0$

$2(n+1)(-K + \sum_{i'=1}^{m'} x_{j'_{i'}}) - (n + m' + \sum {\text{pull-ups}}) = 0$.

Since the sum is 0, it must remain 0 when taken modulo $2(n+1)$, which implies that we can discard all terms containing a multiple of $2(n+1)$ to obtain the new equation

$-(n + m' + \sum {\text{pull-ups}}) = 0$.

This can be directly substituted back into the previous equation to get

$2(n+1)(-K + \sum_{i'=1}^{m'} x_{j'_{i'}}) = 0$.

Finally, dividing both sides by $2(n+1)$ leaves

$-K + \sum_{i'=1}^{m'} x_{j'_{i'}} = 0$,

which yields a solution to the original general problem instance.