1
$\begingroup$

I have a question to the reduction from Vertex Cover into Dominating Set.

So my lecture says if I have a undirected Graph $G = (V,E)$ where $S \subseteq V$ is a vertex cover. Then we construct a new graph $G'$ which has the same vertices of G, except the isolated ones. For each edge $\{u,v\}$ in $G$, we add a new vertex that is connected with $u,v$.

So my question is, why I have to form every edge into triangles? Why is it not enough to only remove the isolated vertices?

Every vertex cover without isloated vertices is a dominating set at the same time

$\endgroup$
1
$\begingroup$

Remember that you also have to care for the reverse direction. In this case, you should see whether every dominating set is also a vertex cover (hint: no, but why?).

$\endgroup$
  • $\begingroup$ But why not? Do you have an example graph where this construction is false? I think its the size of the VC/DS or not? $\endgroup$ – Marc Feb 6 at 19:17
  • $\begingroup$ @Marc Try something like a small complete graph or a small path if those would work. $\endgroup$ – Juho Feb 6 at 20:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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