8
$\begingroup$

You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should belong to exactly one subsequence. Maximize the number of subsequences. It is not required that elements in subsequences are consecutive.

It seems the problem is NP-hard (or "Can the sequence be partitioned into $k$ subsequences which all have zero sums?" is NP-complete), but can't prove it.

Example: the maximal number of subsequences for the sequence [2, 0, 1, -1, -1, -1] is 3: [0], [2, -1, -1] and [1, -1].

$\endgroup$
  • $\begingroup$ Note that NP is a class of decision problems, while this is an optimization problem, so you have to transform it into a decision problem. One way to do this would be to change the problem to "Can the sequence be partitioned into $k$ subsequences which all sum to $0$?" $\endgroup$ – Alex Becker Mar 23 '13 at 22:36
  • $\begingroup$ Also, are you trying to show the problem is in NP, or is NP-complete? $\endgroup$ – Alex Becker Mar 23 '13 at 22:37
  • $\begingroup$ Also posted, with no mention here or there, to MathOverflow. $\endgroup$ – Gerry Myerson Mar 24 '13 at 5:06
3
$\begingroup$

The decision problem of whether a sequence can be partitioned into $k$ subsequences which sum to $0$ is indeed NP-complete. To show this, we can reduce the 3-partition problem (which is strongly NP-complete) to this.

3-partition problem (best formulation for this reduction): Given a sequence $x_1,\ldots,x_{3n}$ of integers between $B/2$ and $B/4$, which sums to $Bn$, determine whether there is a partition of $x_1,\ldots,x_{3n}$ into triples which each sum to $B$. We can assume $B$ is bounded by a polynomial in $n$.

Reduction: Let $N=\max\{4n,B\}$. Consider the sequence of $N$ integers between $-N$ and $N$ given by $$x_1,x_2,x_3,-B,\ldots,x_{3n-2},x_{3n-1},x_{3n},-B,0,\ldots,0$$ which has $m=N-4n$ zeros. The original 3-partition problem is equivalent to whether there is a partition of this sequence into $n+m$ subsequences which sum to $0$.

Proof: If a partition of the original sequence into triples $(x_{i_1},x_{i_2},x_{i_3})$ which add $B$ exists then the $n$ subsequences $(x_{i_1},x_{i_2},x_{i_3},-B)$ and $m$ subsequences $(0)$ sum to $0$. For the converse, note that if a subsequence sums to $0$ and contains a nonzero term, then it must contain at least $4$ nonzero terms, namely three $x_i$ and a $-B$ as all the $x_i$ are positive and it takes at least $3$ to add up to $B$. Thus the sequence can be partitioned into at most $n+m$ subsequences which add up to $0$, and the only way this can be done is if $n$ of the subsequences are of the form $(x_{i_1},x_{i_2},x_{i_3},-B)$ and the other $m$ are simply $(0)$. Thus if it can be partitioned into $n+m$ subsequences, we have $n$ triples $(x_{i_1},x_{i_2},x_{i_3})$ which add to $B$.

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