# Subset Sum: reduce special to general case

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?

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.

• Thank you very much. I wonder, is there a reduction which transforms an instance of 0-subset-sum to one (instead of $n$) instance of K-subset-sum? – ipsec Apr 3 '13 at 16:34
• @ipsec: You mean transform an instance of K-subset-sum to 0-subset-sum? Perhaps taking the union of the $n$ sets above will work. – Aryabhata Apr 3 '13 at 17:31
• Well, I was actually thinking twice whether I got the rigth direction now. When I want to show that K-subset-sum is NP-hard for every K given the fact, that 0-subset-sum is NP-hard, I can use a reduction from 0-subset-sum to K-subset-sum, for which I would need a poly-time transformation from any 0-instance to a K-instance. But I am not certain now that this is actually what I have asked in my question. – ipsec Apr 3 '13 at 19:19
• @ipsec: When you say set $s=0$, you have show the NP-Hardness of $K$-subset-sum given the NP-Hardness of zero-subset-sum: the general problem is at least as hard as the special problem. Note that in reduction terms, you say you have reduced zero-subset-sum to $K$-subset-sum. Also, note that $K$ is an input. When you talk about "every given $K$" what exactly do you mean? The above answer shows that the special case(zero-subset-sum) is as hard (in NP-hardness sense) as the general case ($k$-subset-sum, where $k$ is an input). – Aryabhata Apr 4 '13 at 4:40
• Never mind. What I originally was wondering about is, if we know that 0-subset-sum is NP-hard, can we derive, that e.g. 1-subset-sum is as well? Wikipedia says so, but I was looking for a proper reduction. However I see now that my wording was totally messed up and I was in fact asking the opposite. Anyway you gave me enough input to reduce from any K-subset-sum instance to a L-subset-sum instance for any given integers K and L, so my problem is still solved. – ipsec Apr 4 '13 at 15:08

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.