19
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – ipsec Apr 3 '13 at 16:34
  • $\begingroup$ @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. $\endgroup$ – Aryabhata Apr 3 '13 at 17:31
  • $\begingroup$ 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. $\endgroup$ – ipsec Apr 3 '13 at 19:19
  • $\begingroup$ @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). $\endgroup$ – Aryabhata Apr 4 '13 at 4:40
  • $\begingroup$ 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. $\endgroup$ – ipsec Apr 4 '13 at 15:08
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.