NP hardness of dominating set (reduction from Vertex Cover)
Definitions
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.
Problem
Is there a dominating set of vertices of a specific size?
Reduction
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'\).
Proving
Definitions
\(|V*| = n\)
\(m\) = no of isolated vertices in \(V*\)
\(k\) = vertex cover of \(G*\)
Steps
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.
