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

Problem Detail: 

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.

Asked By : hengxin

Answered By : Vor

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19092