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


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?).

  • $\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 '19 at 19:17
  • $\begingroup$ @Marc Try something like a small complete graph or a small path if those would work. $\endgroup$
    – Juho
    Feb 6 '19 at 20: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.