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


1 Answer 1


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

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.