1
$\begingroup$

After asking this question I was thinking about some variants of subset sum problem (SSP).

The usual subset problem is the following.

  • Instance: Given a set of $n$ integers and an integer $\sigma$.
  • Question: Is there a non-empty subset that sums to $\sigma$?

The three variants of subset sum that I thought about are (I assume that all integers are positive):

  1. SSP1:
    • Instance: Given a set of $n$ integers $\{a_1,\ldots,a_n\}$, an integer $k\leqslant n$ and and integer $\sigma$.
    • Question: Is there a non-empty subset of cardinality at most $k$ that sums to $\sigma$? That is a subset $S$ for which $\sum_{i\in S}a_i=\sigma$ and $|S|\leqslant k$?
  2. SSP2:
    • Instance: Given a set of $n$ integers $\{a_1,\ldots,a_n\}$, an integer $k\leqslant n$ and and integer $\sigma$.
    • Question: Is there a non-empty subset of cardinality at most $k$ that sums to at most $\sigma$? That is a subset $S$ for which $\sum_{i\in S}a_i\leqslant\sigma$ and $|S|\leqslant k$?
  3. SSP3:
    • Instance: Given a set of $n$ integers $\{a_1,\ldots,a_n\}$, an integer $k\leqslant n$ and and integer $\sigma$.
    • Question: Is there a non-empty subset of cardinality at most $k$ that sums to at least $\sigma$? That is a subset $S$ for which $\sum_{i\in S}a_i\geqslant\sigma$ and and $|S|\leqslant k$?

My question is: Are these problems (SSP1, SSP2 and SSP3) hard?

My claim is the following: SSP1 is NP-complete but SSP2 and SSP3 are polynomial-time solvable.

My Proof (intuitive and incomplete):

  • For SSP1, if I can find a subset $S$ of cardinality at most $k$, then $S\neq\emptyset$ and hence I have solved SSP.
  • For SSP2, sort $\{a_1,\ldots,a_n\}$ in the ascending order. Select the first $k$ elements. If their sum is less than $\sigma$ then we are done. Else remove the biggest elements of the selected $k$ elements and see. Continue.
  • For SSP3, sort $\{a_1,\ldots,a_n\}$ in the descending order. Select the first $k$ elements. If their sum is greater than $\sigma$ then we are done. Else output no.

Is my work correct?

$\endgroup$
  • $\begingroup$ 1. Please ask only one question per post. 2. What have you tried? What specifically are you unsure about? If you have an idea for a possible proof, why not try to flesh out the proof and check each step to see if it follows from all the previous ones? What specifically are you stuck with? We expect you to try everyone you can on your own before asking here. $\endgroup$ – D.W. Jan 23 '16 at 22:52
  • $\begingroup$ Also, we discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jan 23 '16 at 22:52
  • $\begingroup$ Also, by Corollary 5.1, if ETH then SSP1 is not FPT. ​ ​ $\endgroup$ – user12859 Jan 24 '16 at 5:29
3
$\begingroup$

Your work is mostly correct:

  • SSP1 is clearly in NP. Moreover, it is NP-hard by reduction from SUBSET-SUM: given an instance of SUBSET-SUM, reduce it to the corresponding instance of SSP1 with $k = n$.

  • SSP2: Let $m$ be the number of negative elements in $\{a_1,\ldots,a_n\}$, and let $S$ be the sum of the $\min(m,k)$ smallest of them. Check whether $S \leq \sigma$. This is a polynomial time algorithm.

  • SSP3: Can be reduced to SSP2 by negating the set and $\sigma$. (We can also solve it directly just like SSP2.)

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