4
$\begingroup$

Background: The Exact-3D-Matching problem is defined as follows (The definition is from Jeff's lecture note: Lecture 29: NP-Hard Problems. You can also refer to 3-dimensional matching):

Exact-3D-Matching: Given a set $S$ and a collection of three-element subsets of $S$, called triples, is there a sub-collection of disjoint triples that exactly cover $S$?

The 3-Partition problem is defined as (It is also from Lecture 29: NP-Hard Problems. You can also refer to 3-partition problem.):

Given a set $S$ of $3n$ integers, can it be partitioned into $n$ disjoint three-element subsets, such that every subsets has exactly the same sum?

It is known that the 3-Partition problem can be proved to be NP-complete by reducing the NP-complete Exact-3D-Matching problem to it. And the NP-completeness of the Exact-3D-Matching problem is proved by reducing the 3SAT problem to it (both are given in the book Computers and Intractability: A Guide to the Theory of NP-Completeness).

Problem: My problem is:

How to prove the NP-completeness of the Exact-3D-Matching problem by reducing the 3-Partition problem to it?

I have found neither papers nor lecture notes on it.

$\endgroup$
2
  • 1
    $\begingroup$ after posting an answer, I noticed that the title asks for the reverse direction; you should change it (or change the question and ignore my answer :-) $\endgroup$
    – Vor
    Dec 18, 2013 at 16:52
  • $\begingroup$ Oops... It is my mistake. Your answer is exactly what I am asking for. The reduction from Exact-3D-Matching to 3-Partition can be easily found (although the reduction itself is not easy) in textbooks. Therefore, I am asking for the reverse direction. I will change the title and accept your answer. $\endgroup$
    – hengxin
    Dec 19, 2013 at 11:12

1 Answer 1

1
$\begingroup$

I think this reduction should work:

Given a 3-PARTITION instance: $n$ integers $a_1,\ldots,a_{3n}$ and a target sum $B$; mark each integer with an unique identifier $\hat{a_i}$; then build a collection of 3-elements subsets $C_j = \{ \hat{a}_{i_1}, \hat{a}_{i_2}, \hat{a}_{i_3} \}$ such that $a_{i_1}+ a_{i_2}+ a_{i_3} = B$ and $i_1 \neq i_2 \neq i_3$ (the collection has $O(n^3)$ elements).

The original 3-PARTITION problem has a solution if and only if there exist an EXACT-3D-MATCHING $C_{j_1}, \ldots, C_{j_n}$ that covers $S = \hat{a}_{1}, \ldots, \hat{a}_{3n}$.

For example given $A = \{5,4,3,3,3,2,2,1,1\}, B = 8$ we build: $S = \{5a,4a,3a,3b,3c,2a,2b,1a,1b\}$ and the collection of 3-elements subsets:

C1  = { 5a, 2a, 1a }
C2  = { 5a, 2a, 1b }
C3  = { 5a, 2b, 1a }
C4  = { 5a, 2b, 1b }
C5  = { 4a, 3a, 1a }
C6  = { 4a, 3a, 1b }
C7  = { 4a, 3b, 1a }
C8  = { 4a, 3b, 1b }
C9  = { 4a, 3c, 1a }
C10 = { 4a, 3c, 1b }
C11 = { 4a, 2a, 2b }
C12 = { 3a, 3b, 2a }
C13 = { 3a, 3b, 2b }
C14 = { 3a, 3c, 2a }
C15 = { 3a, 3c, 2b }
C16 = { 3b, 3c, 2a }
C17 = { 3b, 3c, 2b }

An Exact-3D-MATCHING is given by:

C1  = { 5a, 2a, 1a }
C6  = { 4a, 3a, 1b }
C16 = { 3b, 3c, 2b }

that also uniquely identifies a valid solution for the original 3-PARTITION problem.

$\endgroup$
1
  • $\begingroup$ Yes, it works. I failed to mark each $a_i$ unique. Thanks. $\endgroup$
    – hengxin
    Dec 19, 2013 at 11:16

Your Answer

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

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