0
$\begingroup$

The 3-Dimensional Matching Problem is relatively well known in the fields of discrete mathematics and computer science. The problem consists of determining whether a tripartite $3$-hypergraph with parts of equal cardinality has a perfect matching. It is listed as one of the (many) NP-Complete problems.

I imagine proofs of its NP-Completeness vary, but I'm particularly looking for a proof that $3$-SAT $\leq_\rho $ 3-Dimensional matching, where $A \leq_\rho B$ means $A$ is Karp-reducible to $B$. I can't find a source with this proof, however.

The required proof must $a.$ provide an algorithm that maps from an instance of $3$-SAT to a tripartite $3$-hypergraph, and prove that such instance is satisfiable iff there is a perfect matching in the constructed $3$-hypergraph.

Anybody knows the proof (or a source with it)? Thanks.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I believe page 50 of the book "Computers and Intractability: a Guide to the Theory of NP-Completeness" (by Garey and Johnson, 1979) gives you the exact proof you want.

$\endgroup$
2
  • $\begingroup$ It does. Thank you! $\endgroup$
    – lafinur
    Commented Jun 25 at 23:35
  • $\begingroup$ My pleasure indeed! $\endgroup$
    – B. Highwood
    Commented Jun 25 at 23:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .