19
$\begingroup$

Wikipedia states the subset sum problem as finding a subset of a given set of integers, whose sum is zero. Further it describes it as 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

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.