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$.

Fix $1 \le k \le |V|$ and construct an instance of the exact cover problem as follows:

• The elements to be covered are those in $E$ plus $k$ additional elements $x_1, \dots, x_k$.
• There are $7k$ sets for each vertex $v \in V$, namely all sets $X \cup \{x_i\}$ for $X \in 2^{E_v} \setminus \{ \emptyset \}$ and $i=1,\dots,k$. Let $S_v$ be the collection of such sets for $v$.
• Finally, there are $k$ sets $\{x_1\}, \{x_2\}, \dots, \{x_k\}$.

If there is an exact cover $C$ for this instance, then we must have $|C| \le k$ (since each set contains one of $x_1, \dots, x_k$) and hence there is a vertex cover of $G$ of size at most $k$. Namely: $\{ v \in V \mid S_v \cap C \neq \emptyset\}$.

Suppose now that there is a vertex cover $C$ of $G$ with at most $k$ vertices. Let $C=\{v_1, \dots, v_\ell \}$. We now show that the above exact cover instance admits an exact cover. Arbitrarily assign each edge $(u,v)$ of $G$ to one of the vertices in $\{u,v\} \cap C$. For a vertex $v_i \in C$, let $A_i$ be the set of edges assigned to $v_i$. For $i>\ell$ let $A_i = \emptyset$. The sought exact cover contains all sets $A_i \cup \{x_i\}$ for $i=1,\dots, k$. Notice that if $A_i \neq \emptyset$ then $A_i \cup \{x_i\} \in S_v$.

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.