0
$\begingroup$

I am trying to reduce the vertex cover (decision) problem to the dominating set (decision) problem in order to prove that the latter is NP-hard. After some research online, I found that many articles use a reduction that transforms the input for the vertex cover problem to an input for the dominating set problem by creating a triangle for each edge. Here is one of such articles (See question 7 in the link).

The question that I would like to ask is, if we drop isolated vertices in the input to the dominating set problem, then, we could easily find a counterexample to the reduction - Let the input to the vertex cover problem be a graph containing $N$ isolated nodes and parameter $k=N$. Now, the input to the dominating set problem will clearly be an empty graph with the parameter $k=N$. Now, there is a vertex cover of size $N$. But it is not a dominating set of the transformed graph (i.e. the answer to the vertex cover problem is yes but the answer to the dominating set cover problem is no).

How could I fix the reduction? Could someone please advise me?

$\endgroup$
1
$\begingroup$

If I understand correctly you only have a problem when the graph $G = (V,E)$ of the vertex-cover instance has isolated vertices. In this case you can transform $G$ into a related graph $G' = (V \cup \{x,y \}, E')$ by adding a two new vertices $x$ and $y$ such that $x$ and $y$ are connected to each other by an edge, and there is an edge between $x$ and each other vertex in $V$. Formally: $E' = E \cup \{ (x,v) \mid v \in V \cup \{y\}\}$.

If $G$ admits a vertex-cover $C$ of size at most $k$, then $G'$ admits a vertex-cover of size at most $k+1$, namely $C \cup \{ x \}$.

If $G'$ admits a vertex-cover $C$ of size at most $k+1$, then $G$ admits a vertex-cover of size at most $k$. This can be easily seen by noticing that $C \setminus \{ x, y\}$ must cover all the edges in $E$, and that $(x,y) \in E'$ ensures that at least one of $x$ and $y$ is in $C$, i.e., $|C \setminus \{ x, y\}| = |C| - |C \cap \{x,y\}| \le |C| - 1 \le k$.

Since $G'$ has no isolated vertex, you can now safely transform it to the graph $H$ of the dominating-set instance (using the known reduction). In this way you show that $G$ has a vertex-cover of size at most $k$ $\iff$ $H$ has a dominating set of size at most $k+1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Amazing answer. Thank you! $\endgroup$ – Donald Nov 26 '19 at 1:49

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.