0
$\begingroup$

My problem is the following:

Input: a set of $m$ non-negative integers $\{b_1,...,b_m\}$ and a parameter $n$ with $n<m$.

Output: $n$ sets of 3 numbers

Task: Cut the $b_i$'s into $3n$ integers such that we can gather these numbers in $n$ sets of 3 elements where all the elements in a set are the same.

Example (with $m=4$ integers as input): $b_1=10$, $b_2=9$, $b_3=6$ ,$b_4=5$ and $n=3$.

For this instance, there is a solution since we can cut the $b_i$'s in the following way:

  • $b_1=10=5 + 4 +1$
  • $b_2=9=5 +4$
  • $b_3=6=5+1$
  • $b_4=5=4+1$

So the $n=3$ sets are $\{5,5,5\}$, $\{4,4,4\}$ and $\{1,1,1\}$.

My first question is: how could I show that my problem is NP-hard?

In order to move forward on this question, I thought about a reduction from a 3-PARTITION instance to an instance of my problem (but maybe this idea is not correct, see my second question).

Let $\{a_1,...,a_{3p}\}$ with $\sum_{i=1}^{p}a_i=pB$ be a general 3-PARTITION instance. From this instance of 3-PARTITION, I create an instance of my problem in the following way (see the example below):

We have $n=3p$ and there are $m=7p$ integers which are:

  • $6p$ integers in this way: $b_1=b_{1'}=a_1$, ..., $b_{3p}=b_{3p'}=a_{3p}$
  • $p$ integers in this way: $b_{3p+1}=...=b_{4p}=B$

W.l.o.g, suppose we have a solution of the instance of 3-PARTITION, $B=a_1+a_2+a_3=a_4+a_5+a_6=...=a_{3p-2}+a_{3p-1}+a_{3p}$, it is easy to construct a solution to the instance of my problem by only cutting the $p$ last integers equal to $B$, the cut is denoted $b_{3p+k}=B=b_{3p+k}^{(1)}+b_{3p+k}^{(2)}+b_{3p+k}^{(3)}$.

The solution of my problem is then composed of the $n=3p$ following sets:

  • Set 1: $\{b_1,b_{1'},b_{3p+1}^{(1)}\}$, Set 2: $\{b_2,b_{2'},b_{3p+1}^{(2)}\}$, Set 3: $\{b_3,b_{3'},b_{3p+1}^{(3)}\}$
  • ...
  • Set 3p-2: $\{b_{3p-2},b_{3p'-2},b_{4p}^{(1)}\}$, Set 3p-1: $\{b_{3p-1},b_{3p'-1},b_{4p}^{(2)}\}$, Set 3p: $\{b_{3p},b_{3p'},b_{4p}^{(3)}\}$

And all the elements inside a set are the same since we have a solution to the 3-PARTITION instance.

So, with the previous construction, we have that: if there is a solution to the 3-PARTITION instance $\Rightarrow$ we have a solution to the instance of my problem.

My second question is: what about the other sense? Is it possible to show that if we have a solution to the instance of my problem, it implies that we have a solution of the original 3-PARTITION instance?

One way would be to show that the construction of the $3p$ sets as described above is the unique solution of the instance of my problem. This is the reason why, in the first place, in the instance of my problem, each integer is repeated twice.

Example of the reduction Consider the following instance of 3-PARTITION: $a=\{47,44,43,40,37,35,29,28,27\}$, we have $p=3$ and $\sum_i^9 a_i=3\times 110$.

The instance of my problem is then made of the following $m=21$ integers: $b=\{47,47,44,44,43,43,40,40,37,37,35,35,29,29,28,28,27,27,\color{red}{110},\color{blue}{110},\color{magenta}{110}\}$.

The solution of the 3-PARTITION instance $47+35+28=44+37+29=40+43+27=110$ implies this solution of the instance of my problem with $n=9$ sets:

  • Set 1: $\{47,47,\color{red}{47}\}$, Set 2: $\{35,35,\color{red}{35}\}$, Set 3: $\{28,28,\color{red}{28}\}$
  • Set 4: $\{44,44,\color{blue}{44}\}$, Set 5: $\{37,37,\color{blue}{37}\}$, Set 6: $\{29,29,\color{blue}{29}\}$
  • Set 7: $\{43,43,\color{magenta}{43}\}$, Set 8: $\{40,40,\color{magenta}{40}\}$, Set 9: $\{27,27,\color{magenta}{27}\}$

This illustration shows that if we have a solution of the 3-PARTITION instance, then it is easy to build a solution of my problem.

In terms of this example, the question is: is it possible to show that if we have a solution to the instance of my problem

$b=\{47,47,44,44,43,43,40,40,37,37,35,35,29,29,28,28,27,27,\color{red}{110},\color{blue}{110},\color{magenta}{110}\}$, then we have a solution of the original 3-PARTITION instance (for this particular $b$, it is the case).

For the moment, I am trying to find a counterexample, that is, an instance of my problem for which we do have a solution but which does not imply a solution of the 3-PARTITION instance.

Thank you very much for your help!

$\endgroup$
  • 2
    $\begingroup$ You're asking ask whether your reduction works. Perhaps it does, perhaps it doesn't. Not every reduction you think of works. Try to found a counterexample, and failing that, try to prove that it works. If it doesn't work, you'll have to find a different reduction. Coming up with a candidate reduction isn't enough - you have to tweak your reduction until it works, if at all possible. Unfortunately, we can't do it for you - this is something you have to do on your own. Also, it's the only way to really understand NP-hardness reductions - to struggle with them yourself. $\endgroup$ – Yuval Filmus Dec 29 '15 at 9:19
  • $\begingroup$ @YuvalFilmus Yes, you are right. But I was dealing with this reduction for a while and I just wanted to have an external opinion. Thanks for the advice! $\endgroup$ – user2370336 Dec 29 '15 at 9:44
  • $\begingroup$ For what it's worth, I found an example of an instance of my problem $b=\{37,37,36,36,35,35,28,28,27,27,26,26,25,25,24,24,23,23,87,87,87\}$ for which there is a solution of a different form than the one proposed in my question. We have to cut the integers $\{37,37,36,36,35,35\}$ to form the following $n=9$ sets: $\{25,25,25\}$, $\{24,24,24\}$, $\{23,23,23\}$, $\{12,12,12\}$, $\{28,28,28\}$, $\{27,27,27\}$, $\{26,26,26\}$, $\{9,9,9\}$, $\{87,87,87\}$. Nevertheless, with this example, we still have a solution of the 3-PARTITION instance. So it is still not a counterexample to my reduction. $\endgroup$ – user2370336 Dec 29 '15 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.