4
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user2370336 Oct 9 '15 at 23:44
  • $\begingroup$ @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). $\endgroup$ – D.W. Oct 9 '15 at 23:56
  • $\begingroup$ ♦, 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. $\endgroup$ – user2370336 Oct 10 '15 at 9:25
  • 1
    $\begingroup$ @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.) $\endgroup$ – D.W. Oct 10 '15 at 22:52
  • 1
    $\begingroup$ @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. $\endgroup$ – D.W. Oct 12 '15 at 16:10

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.