4
$\begingroup$

We want to transform $3DM$ to $PARTITION$, I am reading Garey and Johnson book and I really don't understand how they do the transformation, I know how they create elements $a_i$ from triples of set $M = W \times X \times Y$, but I don't know why they add two other elements $b_1$ and $b_2$ with definition $$ s(b_1) = 2 (\sum_{i=1}^{k} s(a_i)) - B \\ s(b_2) = (\sum_{i=1}^{k} s(a_i)) + B $$

with $B$ being: $$ B = \sum_{j = 0}^{3q - 1} 2 ^ { pj} $$ and $p = [log_2(k)] + 1$ and $q$ is the number of elements in $X$ (Y, W also have the same number of elements) and also $k$ is the number of triples in $M$.

It would be very nice if anyone could clarify this transformation.

$\endgroup$
3
$\begingroup$

What they actually do is a composition of two reductions (and some optimization). The first is from 3DM to SUBSET-SUM, and the second is from SUBSET-SUM to PARTITION. For the first part, I have it written down here, and the second reduction is quite well known, e.g. here.

Note that there is a small caveat in the first reduction, where we assume that the numbers are encoded in base $|X|+1$, while SUBSET-SUM requires the numbers to be in binary. The reduction you mention does the conversion explicitly, which accounts for the strange $p$ you encountered (which is just the base-conversion constant).

$\endgroup$

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.