0
$\begingroup$

I'm trying to show how to reduce the Partition problem to the 3-Partition problem.
I'll first describe the problem using the definitions and notations I'm familiar with (I hope they're legit), and will then ask my question.
So, the Partition problem is as follow:
Given a multiset of integers $X$, we have to decide whether or not $X$ can be partitioned into two sub-sets $A,B$ such that $\sum_{x_i\in A}x_i=\sum_{x_i\in B}x_i$.
In the 3-Partition problem, given a multiset of integers $Y$, we have to decide whether or not $Y$ can be partitioned into three sub-sets $A,B,C$ such that $\sum_{x_i\in A}x_i=\sum_{x_i\in B}x_i=\sum_{x_i\in C}x_i$.

I want to show a reduction $Partition\leq _p 3Partition$, That is, to show that given $X$ as input for the Partition problem, I can build $Y$ as input for the 3-Partition problem, s.t. $X$ can be partitioned to two iff $Y$ can be partitioned to three.
So given $X$, let $\sum_{x_i\in X}x_i=m$, and define $Y$ as:
$Y=\left \{ x_1, x_2,...,x_n,\frac{m}{2}|x_i\in X \right \}$.

Proof:
The first direction is easy: suppose that $X$ can be partitioned to two sub-sets $A,B$ s.t. the above conditions hold, then $Y$ can be partitioned to three: $A,B,C$, while $C=\left \{\frac{m}{2} \right \}$.
I'm stuck with the second direction: suppose that $Y$ can be partitioned to three, why does that guarantee that $X$ can be partitioned to two?

b.t.w, how can I be sure that $\frac{m}{2}$ is an integer? do I even have to pay attention to it?

$\endgroup$
3
$\begingroup$

To answer your bolded question: The sum of the numbers in $Y$ is $\frac{3m}2$. Thus $A$, $B$, and $C$ each need to be of size $\frac m2$. This can only be achieved by partioning as in the first direction.

Regarding your second question: You can not be sure that $\frac m2$ is an integer and you have to pay attention to it, in order to get a formally correct reduction.

The easiest way to address this is by having your reduction function distinguish two cases: If $\frac m2$ is an integer, it proceeds as you describe. If $\frac m2$ is not an integer, it exploits the fact that in this case the answer to the original question ("Can $X$ be partitioned?") is easy. I'll leave it as an exercise to figure out the details of this case.

$\endgroup$
  • $\begingroup$ Perfect. and just correct me if I'm wrong: if $\frac{m}{2}$ is not an integer, then the answer to the original question is "no", since $m$ must be even for an equal partition to be possible. $\endgroup$ – so.very.tired Apr 5 '14 at 12:32
  • 1
    $\begingroup$ That's correct. $\endgroup$ – FrankW Apr 5 '14 at 12:34

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.