Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Subset-sum: Given a list of numbers, find if a non-empty sublist has sum 0 (there's a variation where we want sum=k instead of 0, but 0 is easier for analysis)

Partition: Given a list, can it be partitioned into two non-empty sublists with equal sum?

I want to reduce subset-sum to partition. The reductions I found so far are same as this one but it has following faults :

  1. For $B=0$, you can always partition $L'$ into $\{2S-0\}$, $\{S+0\} U L$.
  2. It supposes $2S-B$ and $S+B$ have to go to different partitions! You could have both of them in same partition along with elements that sum to $-S$, hence total sum $= 2S$ as needed.
share|improve this question
2  
Shouldn't this be a comment on the answer you link to? –  Raphael Nov 24 '12 at 20:16
    
didn't want to dig up an old grave, and didn't think i would get replies over there ... –  Karan Nov 24 '12 at 20:19
    
Users get notified when somebody comments on their posts, and Yuval is an active user. But never mind, you don't have the rep to comment, anyway. I think this is a fair question to post, and I suspect Yuval will give you an answer. –  Raphael Nov 24 '12 at 20:20

1 Answer 1

up vote 4 down vote accepted
  1. You're absolutely right that this partition always occurs. If you consider what this means in terms of the corresponding subset, you'll find that this indicates that the empty set (which is always a subset) has sum 0. In fact, this indicates the there is always a solution to subset sum when the target is 0, which is exactly as expected. It turns out fixing the target sum to 0 does not just make the problem easier to discuss, it makes it easier in a complexity sense ($O(1)$ by outputting YES immediately).

  2. You're right here too. There is a formulation of subset sum where the input is a list of positive integers, and I think the reduction you are reading was from that language. The goal was to have our added elements be large enough that they cannot both go in the same part. To patch that up, we can use the sum of the absolute values. This actually shows some of the structure of the proof better, because $2S$ was actually $S +$ some-large-enough-number-for-which-$S$-will-suffice-but-so-do-larger-numbers.

At this point I'm copy-pasting from the linked post and just editing to handle negatives:

Let $(L,B)$ be an instance of subset sum, where $L$ is a list (multiset) of numbers, and $B$ is the target sum. Let $S = \sum L$ and choose $S' > \sum_{l \in L} |l|$. Let $L'$ be the list formed by adding $S'+B,S'+S-B$ to $L$.

(1) If there is a sublist $M \subseteq L$ summing to $B$, then $L'$ can be partitioned into two equal parts: $M \cup \{ S' + S-B \}$ and $L\setminus M \cup \{ S'+B \}$. Indeed, the first part sums to $B+(S'+S-B) = S'+S$, and the second to $(S-B)+(S'+B) = S'+S$.

(2) If $L'$ can be partitioned into two equal parts $P_1,P_2$, then there is a sublist of $L$ summing to $B$. The sum of the two new elements is $(S'+B)+(S'+S-B) = 2S'+S$. All subsets $A \subset L$ have $\left|\sum A\right| < S'$, so it is not possible that $\{S'+S-B\} \cup \{ S'+B \} \cup A$ has sum $S' + S$ (it is always greater). So the two new elements belong to different parts. Without loss of generality, $S'+S-B \in P_1$. The rest of the elements in $P_1$ belong to $L$ and sum to $B$; they do not include a new element, so they are a solution to subset sum.

share|improve this answer
    
I was thinking in term of subset sum as defined on wikipedia where 0 sum is required of a non-empty subset, but not sure if the reduction from that to partition is natural (Is it ?) –  Karan Nov 26 '12 at 5:32
    
Interesting. I actually hadn't seen a formulation that requires non-emptiness. In that case, I would reduce first to the original version (which allows empty sets). Pick a number $S'$ greater than the sum of absolute values and add it to each element. To account for this addition, append $n-1$ copies of $-S'$ to the list. Now make the target $S'$. –  William Macrae Nov 26 '12 at 6:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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