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

ignougroup
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