# Variant of (WEAK) PARTITION with 2 distinct solutions

I am interested in the complexity of the following problem:

Input: A list $a_1\leq ⋯ \leq a_n$ of positive integers.

Question: Are there two vectors $x, x'\in\{−1,0,1\}^n$, with at least one $x_i$ and one $x'_i$ non-zero (the subsets must be non-empty), such that $$\sum_{i=1}^nx_ia_i=0, \sum_{i=1}^nx'_ia_i=0 \text{ and } x_ix'_i=0 \text{ }\forall i.$$ WEAK PARTITION is a variant of PARTITION where we are looking for a partition of a subset of the input, and not a partition of all the integers. This is the reason why we have $\{−1,0,1\}^n$ and not $\{−1,1\}^n$. Note that the subset must be non-empty, it means at least one $x_i$ must be non-zero.

But I am interested in the problem described above where we are looking for two distinct weak partitions. For example, with $A=(1,2,3,4,5,7,11,11)$, we have $x=(1,0,1,0,0,1,-1,0)$, $x'=(0,1,0,1,1,0,0,-1)$ and for each component $i$ we have $x_ix'_i=0$. It means we have two disjoint subsets of $A$ where there is a weak partition.

There is clearly a reduction from WEAK PARTITION but I suspect this problem to be NP-hard in the strong sense. Do you see any reduction from a problem which is NP-hard in the strong sense ?

Thank you very much.

• A trivial solution is $\mathbf{x}, \mathbf{x}' = \mathbf{0}$, are you excluding that? – vonbrand Oct 9 '15 at 16:14
• @vonbrand yes, at least one $x_i$ must be non-zero. – user2370336 Oct 9 '15 at 16:48

No such reduction is likely to exist (unless P=NP). In particular, there's a pseudo-polynomial time algorithm for your problem, so your problem isn't strongly NP-hard (unless P=NP).

The algorithm uses dynamic programming and is a straightforward modification of the dynamic programming algorithm for PARTITION. Define $f(j,y,z)$ to be 1 if there exists two non-zero disjoint vectors $x,x'$ of the required form such that

$$\sum_{i=1}^j x_i a_i = y, \sum_{i=1}^j x'_i a_i = z.$$

Otherwise, $f(j,y,z)=0$. Also define $g(j,y)$ to be 1 if there exists a non-zero vector $x$ such that $\sum_{i=1}^j x_i a_i = y$, or 0 otherwise.

Note that $f,g$ satisfy the following recurrence relations:

\begin{align*} f(j,y,z) = &f(j-1,y,z) \lor f(j-1,y-a_j,z) \lor f(j-1,y+a_j,z) \lor f(j-1,y,z-a_j)\\ &\lor f(j-1,y,z+a_j) \lor (g(j-1,y) \land z=\pm a_j) \lor (g(j-1,z) \land y=\pm a_j).\\ g(j,y) = &g(j-1,y-a_j) \lor g(j-1,y+a_j) \lor g(j-1,y) \lor (y=\pm a_j).\end{align*}

The base cases are $f(0,y,z)=0$ and $g(0,y)=0$ for all $y,z$.

With this recurrence, evaluate $f(j,y,z)$ and $g(j,y)$ for all $0 \le j \le n$ and all $y,z$ satisfying $|y|,|z| \le a_1 + \dots + a_n$. Each such value can be computed in $O(1)$ time using memoization / dynamic programming.

Finally, look at the value of $f(n,0,0)$ that you computed. If $f(n,0,0)=1$, then there is a solution to your problem (i.e., there exists two disjoint vectors $x,x'$ that each represent two disjoint weak partitions).

What's the running time of the algorithm? If the inputs are represented in unary, the number of $f$-values we compute is polynomial in the size of the input, and each $f$-value can be computed in $O(1)$ time using the recurrence relation above. It follows that this dynamic programming algorithm runs in polynomial time, if the inputs are provided in unary.

• Thank you for you answer! But I must confess I do not understand very well the recurrence relation. I implemented and it does not seem to work. I suppose that the terms f(j-1,y+a_jz,) and f(j-1,y,z+a_j) allow to take into account that x_i can be -1, right? But more importantly, I do not see why the two solutions should be disjoint with such a formula. For me, it seems that the relation allows to answer the question: "are there a subset where the sum of the elements are y and a subset where the sum of the elements are z", but nothing prevents that the two subsets have common elements. – user2370336 Oct 9 '15 at 23:44
• @user2370336, $f(j-1,y,z)$ represents the case $x_j=x'_j=0$; $f(j-1,y-a_j,z)$ represents the case $x_j=-1,x'_j=0$; $f(j-1,y+a_j,z)$ represents the case $x_j=+1,x'_j=0$; $f(j-1,y,z-a_j)$ represents the case $x_j=0,x'_j=-1$; $f(j-1,y,z+a_j)$ represents the case $x_j=0,x'_j=+1$. Notice that in all five of these cases, $x_j x'_j=0$. This is how my algorithm enforces that $x,x'$ must be disjoint. In particular, it does prevent the two subsets from having any common elements (the recurrence doesn't include any term like $f(j-1,y-a_j,z-a_j)$, so it doesn't allow $x_j,x'_j$ both non-zero). – D.W. Oct 9 '15 at 23:56
• ♦, ok thanks I understand. That's my fault, I was not specific enough while describing my problem because any subset must contain at least one element ($x=x'=0$ is not a valid solution). Indeed, for any input with at least one integer, we have $f(1,0,0)=1$ because $f(0,0,0)=1$. And clearly, although $f(1,0,0)=1$, we do not have two disjoint weak partitions with only one element. – user2370336 Oct 10 '15 at 9:25
• @user2370336, you're absolutely right -- and no need to apologize; I want to get this right, too. Check my updated recurrence relation and see if it does the right thing now. (Basically, what we need to do is write a recursive algorithm, then memoize it. I keep having small bugs in my recursive algorithm. So if you need to do it yourself, you now know how to do it.) – D.W. Oct 10 '15 at 22:52
• @user2370336, I see the problem. We need to calculate $g(j,y)$ for both positive and negative values of $y$ (e.g., for $-5 \le y \le 5$), and $f(j,y,z)$ for both positive and negative values of $y,z$. I updated the answer. That will make it work correctly for the example you gave. – D.W. Oct 12 '15 at 16:10