Is the following problem NP-hard:

Input: $A\subset\mathbb Z, k\in\mathbb N$
Question: is there a multiset of indices $I$, such that $|I|=k$ and $\sum_{i\in I} a_i=0$?

For example, on the input $A=\{-1,2\}, k=3$ we can take $I=\{1,1,2\}$ and thus we get $|I|=3$ and $a_1+a_1+a_2=(-1)+(-1)+2=0$, as desired.

  • $\begingroup$ I know that there's an easy reduction from Subset Sum problem to inputs of the form $A,k$ where $I$ should be a set. Also, I know that there's an easy reduction from this problem to Subset Sum problem by taking $A$ to be a multiset (each element of $A$ should appear $k$ times in the output of the reduction). But I am stuck showing the required reduction. $\endgroup$ – Dudi Frid Apr 28 '17 at 13:12
  • 1
    $\begingroup$ I think that careful analysis of the standard reduction from Vertex Cover to Subset Sum will show that you can actually use a multiset, and it wouldn't matter. But I didn't check the details, and it seems like an inelegant solution anyway. $\endgroup$ – Shaull Apr 28 '17 at 13:34
  • 1
    $\begingroup$ @orlp, why are you thinking that? Each element of $I$ is supposed to be an index, so in the example it must be either 1 or 2 (as $|A|=2$, i.e., $a_1=-1$, $a_2=2$). $\endgroup$ – D.W. Apr 28 '17 at 14:31
  • 1
    $\begingroup$ @nick.schachter, why does that suggest the problem is not NP-hard? If we were limited to $k=3$, then the results about 3-sum would suggest that the problem is not NP-hard. But in this question $k$ is not limited to $k=3$; $k$ can be arbitrarily large, and thus those methods don't yield a polynomial-time algorithm. $\endgroup$ – D.W. Apr 29 '17 at 0:42
  • 1
    $\begingroup$ If 0 is present in $A$, the answer is trivially yes if I correctly understood the problem. (However, the case "at most k" may still be interesting to study). $\endgroup$ – user53923 May 2 '17 at 9:36

It is NP-hard.

Consider the following two variants:

Variant 1:

Input: $A\subset\mathbb N$, $s\in\mathbb N$.
Question: is there a set of indices $I$, $\sum_{i\in I} a_i=s$?

Variant 2:

Input: $A\subset\mathbb N$, $k\in\mathbb N$, $s\in\mathbb N$.
Question: is there a multiset of indices $I$, such that $|I|=k$ and $\sum_{i\in I} a_i=s$?

It is easy to see variant 1 is NP-hard. It is also easy to reduce variant 2 to your variant in polynomial time by transforming each element $e$ in an instance of variant 2 to $ke-s$. So if we can prove there is a polynomial-time reduction from variant 1 to variant 2, the proof is completed.

The reduction from variant 1 to variant 2 is exactly the same as the one posted by Kristoffer Arnsfelt Hansen in this answer. I rewrite it here for consistency of symbols.

Given an instance of variant 1, assume that $a_i < B$ for all $i$. We will have two new elements for each old element, simulating whether the element is used 0 or 1 times. For element $a_i$ we get two new elements $a^1_i = (2^{n+1} + 2^i)nB + a_i$ and $a^0_i = (2^{n+1} + 2^i)nB$. The new target sum is defined as $s' = (n2^{n+1} + 2^n + \dots + 2^1)nB + s$. The number of elements required in a solution is set to be $n$.

Note in a valid solution of the new instance, for each $i$, the number of $a_i^1$ and that of $a_i^0$ must be exactly $1$ in total, so there is exactly $n$ elements in a valid solution. This is indeed a polynomial-time reduction from variant 1 to variant 2.

| cite | improve this answer | |

Assuming that the algorithm for your problem returns the yes/no answer together with the actual multi-set $I$ itself, then we can build a reduction from sub-set sum to your problem by sending your algorithm several $k$'s starting with $k=N,(|A|=N)$ down to $k=2$, where each time we check for repetitiveness to make sure we have a valid minimum sub-set sum. That would be running your algorithm $N-1$ times each time checking validity which sums up to $N(N-1)$ times your algorithm's running time. Conclusion, your problem is NP-Hard.

Note: Even if your algorithm does not return the actual sub multi-set it can be obtained by repeatedly removing one of the set's elements and checking that the sub multi-set still exists.

| cite | improve this answer | |
  • $\begingroup$ How do you handle repetitiveness? Could you please explain more? $\endgroup$ – xskxzr Mar 11 '18 at 8:18

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.