# 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.