0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The problem with this reduction is that in the vertex cover problem, one is given a positive integer $k$ as well, which should serve as a bound on how many sets one can select in the exact cover. In other words, the vertex cover problem cannot be solved through this reduction, as in the worst case scenario, since exact cover isn't about minimizing the number of sets selected, your reduction will select all vertices in the vertex cover instance. $\endgroup$
    – J. Schmidt
    May 3, 2022 at 9:28
  • 1
    $\begingroup$ @J.Schmidt. Fixed, thanks! $\endgroup$
    – Steven
    May 3, 2022 at 11:21
  • $\begingroup$ This seems to be correct, thanks for the quick correction! $\endgroup$
    – J. Schmidt
    May 3, 2022 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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