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 the3-Partition
problem to it?
I have found neither papers nor lecture notes on it.
Exact-3D-Matching
to3-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$