In exact cover, we're given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise disjoint.
I'm wondering how we can show 3-dimensional matching $\le_p$ exact cover. Given an instance of the 3-dimensional matching problem, can we construct an equivalent instance of exact cover? I know the answer is yes, since the two problems are NP-complete, but how will the reduction look?
In 3D-Matching, we are given $X, Y, Z, T$ where:
1) $X, Y$ and $Z$ are 3 disjoint sets, each of size n.
2) $T = \{(x, y, z)\;:\; x \in X, y \in Y, z \in Z \} \subseteq X \times Y \times Z$
and we have to find M such that:
1) $M \subseteq T$
2) $|M| = n$
3) For any 2 distinct elements of M, $(x,y,z)$ and $(x', y', z')$, $x \neq x', y \neq y' $ and $z \neq z' $
In Exact-Cover, we are given a collection S, k where:
1) S is a collection of subsets of some Universe U with $\cup S=$U
and we have to find $S' = \{S_1, S_2, ..., S_k\} \subseteq S$ such that:
1) The elements in $S'$ are pairwise disjoint
2) $\cup S_i=\;$U
The reduction from 3D-Matching to Exact-Cover is:
Let $S = \{\;\{x, y, z\}\;:\;(x,y,z) \in T\}$
Let $k = |X| = |Y| = |Z| = n$
Now, we prove why the reduction works:
Suppose M is a solution to 3D-Matching.
Let $S' = \{ \{ x,y,z \}: (x,y,z) \in M \}$
Since, $|M|=n$, we have $|S'|=n=k$
We know that if $(x, y, z)$ and $(x', y', z')$ are 2 distinct elements in $M$
that $x \neq x', y \neq y'$ and $z \neq z'$ and since, $X, Y, Z$ are disjoint, this means $\{x,y,z \} \cap \{x', y', z' \} = \emptyset$.
That is, the elements in $S'$ are pairwise disjoint.
Also, $\cup S=$ U = $\cup S'$. Hence, $S'$ covers U.
Hence, $S'$ is a solution to Exact-Cover.
Now, suppose that $S' = \{S_1, S_2, ..., S_k \}$ is a solution to Exact-Cover.
Let $M = \{ (x, y, z): \{ x,y,z \} = S_i\;for\; i=1,2,..k\}$
Since, the $S_i$'s are pairwise disjoint, if (x, y, z) and (x', y', z') are 2 distinct elements of M, it follows that $x \neq x', y \neq y'$ and $z \neq z'$.
Hence, M is a solution to 3D-Matching.
