0
$\begingroup$

I want to show that the multi-dimensional Equal-Subset-Sum is NP-complete in the strong sense: Given a set of $d$-dimensional vectors of non-negative integers, does there exist two distinct nonempty subsets of vectors that sum up to the same vector?

I know from [1] that it is weakly NP-complete when $d=1$, but I don't find any references for the strong hardness in the multi-dimensional case when the dimension is part of the input.

The standard path to show that Equal-Subset-Sum is NP-complete is: $\text{ SUBSET SUM } \leq_p \text{ PARTITION } \leq_p \text{ EVEN ODD PARTITION } \leq_p \text{ EQUAL SUBSET SUM }$

By mimicking the reductions in a multidimensional way, I can get the result I want, but that seems a long stretch for a result that seems "obvious" at first sight (when knowing that Equal-Subset-Sum is weakly NP-complete)

Are there some shortcuts to get this result?

Some ideas:

  • Can we reduce the scalar version to the multidimensional version by writing the values in some well-chosen basis, with some kind of transformation that avoids carrying in the sum?
  • Is there some reference directly to one of the problems in the reduction chain?
  • Can we directly find a completely new reduction to the EQUAL SUBSET SUM?

[1] : Woeginger, Gerhard J.; Yu, Zhongliang, On the equal-subset-sum problem, Inf. Process. Lett. 42, No. 6, 299-302 (1992). ZBL0772.68059.

$\endgroup$
2
  • $\begingroup$ Have you checked out other proofs of strong NP-hardness? I think many give reductions from 3D-matching. The proof that PARTITION-PRODUCT is strongly NP-hard is interesting. 3-PARTITION may also be useful. $\endgroup$
    – Neal Young
    Mar 15 at 17:17
  • $\begingroup$ @NealYoung It is pretty easy from X3C to have the multidimensional case for SUBSET SUM, but I struggle for PARTITION. I just found a reference that shows that finding a $\{-1, 0, 1\}$ eigenvector for $\lambda=1$ is $NP$-complete, and the reduction suggest that it is true even if the matrix is $\{-1, 0, 1\}$, which is basically what I want, except I don't want negative value, but I think that I can reduce from this or adapt the proof. $\endgroup$
    – caduk
    Mar 15 at 17:55

2 Answers 2

1
$\begingroup$

EDIT: I did not answer the original question about EQUAL SUBSET SUM but instead described a reduction for the PARTITION version. I am leaving it here since the OP found this answer useful. It may be possible to tweak the reduction to show a direct reduction for EQUAL SUBSET SUM.

There seems to be an easy reduction for X3C (Exact-3-Cover) with the additional condition that each element belongs to exactly 3 sets. Equivalently this is a 3DM instance in which the degree of each vertex is exactly 3. Let $n$ be number of vertices and $m = 3n$ be number of hyperedges. For each hyperedge $e_i$ create a $n$-dimensional vector with 1 in dimension $j$ if $v_j \in e_i$ and 0 otherwise. Create an additional all 1s vector. Total sum of all vectors is the all 4s vector because degree of each vertex is exactly 3. Only way to get the desired partition of vectors is for the vector sum in each part to be the all 2s vector. This is possible only if the set of vectors that are in the part with the all 1s vector correspond to a perfect matching.

$\endgroup$
1
  • $\begingroup$ Thanks, this is for PARTITION right, not EQUAL SUBSET SUM? Still, this interests me to have an easy reduction to PARTITION, with binary values which I did not have (I had either negative values or a bound linear on the number of vectors). $\endgroup$
    – caduk
    Mar 15 at 23:32
0
$\begingroup$

I think I got a reduction by combining the reduction from @Chandra and idea from other reductions to avoid passing by ODD EVEN PARTITION.

As in Chandra's reduction, we reduce from restricted X3C and build the same vectors $x_1, ..., x_k$ of size $3q$. We add $k-1$ new vectors $y_1, ..., y_{k-1}$ of zeros. For all $i=1...k-1$, we add a new component for the vectors which is $1$ for $x_i$ and $x_{i+1}$, $2$ for $y_i$ and $0$ for the others.

For example, By taking the 3-regular hypergraph $\{1, 2, 3\}, \{1, 2, 4\}, \{1, 2, 5\}, \{4, 5, 6\}, \{3, 5, 6\}, \{3, 4, 6\}$, we get the following matrix: $$\begin{array}{cc} & \begin{array}{l@{{}={}}c} x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & y_1 & y_2 & y_3 & y_4 & y_5 & y_6\\ \end{array} \\ & \left[ \begin{array}{ccccccc|cccccc} 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 2 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 2\\ \end{array} \right] \end{array}$$

From two subsets, we easily build a solution by dispatching the partition from $x_1, x_2, ..., x_5$ in the two subsets. For all $i=1...k-1$, if $x_i$ is in a different subset than $x_{i+1}$ then the If some $x_i$ is in one of the subsets, then row $x_i$ imposes that $x_i+1$ must also be in a subset. If $x_i$ and $x_{i+1}$ are in different subsets, the sums in row $3q+i$ match, otherwise, we add $y_i$ to the other subset (so for row $3q+i$, we get $1+1$ in a subset and $2$ in the other).

Now, suppose we have two disjoint non-empty subsets of vectors that sums to the same vector. We cannot have only $y_i$ in the subsets, so there is at least a $x_i$ that is chosen. If $x_i$ is chosen in a subset, row $3q+i$ ensure that $x_{i+1}$ too must appear in on the subsets. Step by step, if one $x_i$ is in some subset, all the $x_i$ must belong to a subset, hence we will get a partition of the $x_i$.

$\endgroup$
1
  • $\begingroup$ You may want to add details for others to understand/verify your construction. $\endgroup$ Mar 16 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.