NP hardness of dominating set (reduction from Vertex Cover)

Vertex Cover


We have a graph \(G = (V, E)\).

We define the dominating set, \(V'\) to be a subset of of \(V\).

For all edges in E, one of the vertices of the edge has to in \(V'\).

If there is a vertice not part of any edge, it should be in \(V'\) as well.


Is there a dominating set of vertices of a specific size?


We want to find a vertex cover for a graph, \(G* = (V*, E*)\).

Transform this graph into \(G = (V, E)\).

Initialize \(V = V*, E = E*\).

For every edge in \(E*\):

  • create a new vertex \(v_{x,y}\), add to V.
  • create 2 edges \((x, v_{x, y})\) and \((y, v_{x, y})\), add to E.

Assertion we want to prove

Show that \(G*\) has a vertex cover of size \(k\), iff \(G\) has a dominating set of \(k'\).



\(|V*| = n\)

\(m\) = no of isolated vertices in \(V*\)

\(k\) = vertex cover of \(G*\)


Vertex cover, k excludes isolated vertices. As such we need to add it in.

k’ = k + m.

Show if k -> k’

v1, …, vk = vertex cover of \(G*\).

u1, …, um = isolated vertices in \(V*\).

We want to show V1 = {v1, …, vk, u1, …, um} is a dominating set in G.

For any vertex v not in V1, it is not an isolated vertex, otherwise it would have been included.

If v ∈ V*, there is some vertice in V1, such that v forms an edge with it (definition of vertex cover).

If v ∉ V*, v_{x, y} for some edge (x, y) in V*. One of x / y is in \({v1, ..., vk}\).

|V1| = k + m = k’.

Show if k’ -> k

Transform \(V1\), such that if there are any \(v_{x, y}\) nodes, we can swap them out for x / y to get a dominating set of the same size.

Let Vn = {v1, …, vk} be set of all the non-isolated vertices in the dominating set.

Consider an edge x, y, where none of x, y is in Vn.

Then \(v_{x, y}\) is not dominated by the dominating set, which is a contradiction.