How to prove Exact cover problem is NP Complete using Vertex Cover problem?

Question

Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can't find a solution yet to derive it from Vertex Cover.

Answer 1

You can reduce from vertex cover in cubic graphs since it is known to be $\textrm{NP}$-hard. Let $G=(V,E)$ be the graph in the instance of vertex cover and, for $v \in V$, call $E_v = \{ (v,u) \mid (v,u) \in E \}$ the set of edges incident to $v$ in $G$.

Construct an instance of the exact cover problem as follows:

• The elements to be covered are those in $E$.
• There are $7$ sets $S_1^v, \dots, S_7^v$ for each vertex $v \in V$, namely those in $2^{E_v} \setminus \{ \emptyset \}$.

If there is an exact cover $C$ for this instance, then there is a vertex cover of $G$ of size at most $|C|$, namely $\{ v \in V \mid \{S_1^v, \dots, S_7^v\} \cap C \neq \emptyset\}$.

If there is a vertex cover $C$ of $G$, then there is an exact cover of size at most $|C|$. Arbitrarily assign each edge $(u,v)$ of $G$ to one of the vertices in $\{u,v\} \cap C$. For a vertex $v$, let $A_v$ be the set of edges assigned to $v$ and notice that if $A_v \neq \emptyset$ then $A_v = S_i^v$ for some $i \in \{1,\dots, 7\}$. The sought exact cover is then $\{ A_v \mid v \in V \wedge A_v \neq \emptyset \}$.

To conclude the proof you just need to observe that exact cover belongs to $\textrm{NP}$ since the cover itself is a certificate that can be checked in polynomial-time.