4
$\begingroup$

I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is:

Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, find the subset $S$ of the items that maximizes $\sum_{i \in S} w_i$ while keeping this sum at most $W$. Or the decision version: Is there a subset obeying the at-most-$W$ rule with weight at least some number $k$.

So just Knapsack except the values are the weights themselves.

The second and seemingly more common is:

Given a set of $n$ integers, is there a non-empty subset whose sum is 0 (or equivalently, some number $k$)?

E.g., my textbook (Kleinberg and Tardos) as well as this have the first one. Wikipedia and other websites have the second.

I believe both are NP-complete. That said, I haven't found an "obvious reduction" from one to the other that suggests why the two problems are given the same name. So my questions are:

  1. Do quick reductions exists between the two?
  2. Why are these given the same name in the first place?
$\endgroup$
4
  • 1
    $\begingroup$ Reduce the second to the first by taking $k=W$. The other direction is direct (verify first that $k \le W$). $\endgroup$ – Yuval Filmus Feb 18 '20 at 15:55
  • $\begingroup$ @YuvalFilmus Thanks for the response! I understand now how to reduce the second to the first. But as for reducing the first to the second: It seems like you would run into trouble since you only want to know if there is a subset with weight at least some number $k$. Wouldn't checking all numbers from $k$ to $W$ using the second be exponential because it depends on the magnitude of the numbers? $\endgroup$ – kanso37 Feb 18 '20 at 23:13
  • 1
    $\begingroup$ Right. Let’s assume $W-k=2^t$. Add weights $1,2,4,\dots,2^{t-1}$, and ask for a target of $W$. Perhaps a similar approach can be used in general. $\endgroup$ – Yuval Filmus Feb 18 '20 at 23:17
  • $\begingroup$ What a clever technique! Thanks. $\endgroup$ – kanso37 Feb 19 '20 at 0:00
2
$\begingroup$

Given an instance of the second problem, we can easily reduce it to an instance of the (decision version of) the first problem: simply take $W = k$. There is a subset of sum at least $k$ and at most $W$ iff there is a subset of sum exactly $k$.

In the other direction, the idea is to add to the collection a small set of items satisfying the following two properties:

  • The total weight of the new items is $W-k$.
  • Every weight between $0$ and $W-k$ can be represented as a sum of a subset of the new items.

Having added this collection, we ask whether there is a subset summing to exactly $W$. It is not hard to check that there is a subset of the original collection whose sum is between $k$ and $W-k$ if there is a subset of the enlarged collection summing to $W$ exactly.

How do we add these items? The simplest case is when $W - k = 2^t$, in which case we can simply add $1,2,4,\ldots,2^{t-1}$. More generally, suppose $2^t \leq W-k < 2^{t+1}$, and let $W-k = 2^t + C$. We then add $1,2,4,\ldots,2^{t-1},C$.

$\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.