2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.