# Reduction from minimum dominating set to the set cover

To solve the min dominating set problem of a graph G, we can reduce it to a set cover problem.

For example to find the MDS of the graph G:

We can create an instance of the Set Cover problem by:

1. Introducing the universe U to be equal to all vertices of the graph: U={0, 1, 2, 3, 4}.

2. For every closed neighborhood of a vertex in G, we introduce a subset S:

s= {{0, 1}, {0, 1, 2}, {1, 2, 3, 4}, {2, 3, 4}, {2, 3, 4}}

A minimum set cover solution of the instance (s, U) is similar to a minimum dominating set solution in the graph G.

My first question is how we can prove that this reduction is correct, and will give the correct MDS solution for every graph. In our example, the reduction works well and give the correct result.

My second question is how this reduction is related to the reduction when we deal with NP-complete proof(for example we can prove that the MDS problem is NP-complete by reduction to the vertex cover problem).

Are those reductions related? Thank you

Let $$G$$ be an instance of dominating set and construct an instance of $$(U,\mathcal{S})$$ of set cover as you describe. The claim is that $$G$$ has a dominating set of size $$k$$ if and only if there is a subfamily $$\mathcal{S}' \subseteq \mathcal{S}$$ with $$k$$ members that covers $$U$$.
In the first direction, which you indicate is clearer, let $$D$$ be a dominating set of size $$k$$. Construct $$\mathcal{S'}$$ by adding into it the set corresponding to the closed neighborhood of every $$v \in D$$. Clearly, $$\mathcal{S}'$$ has size $$k$$ as $$D$$ has size $$k$$. Further, by the definition of a dominating set, $$\mathcal{S}'$$ also covers $$U$$.
In the second direction, let $$\mathcal{S}'$$ be a set cover for $$U$$. Build $$D$$ such that if the set $$S_v$$, the set corresponding to the closed neighborhood of $$v$$, is in $$\mathcal{S}'$$, add the vertex $$v$$ to $$D$$. Because $$\mathcal{S}'$$ covers $$U$$ which by construction corresponds to the vertex set of $$G$$, we have that $$D$$ is a dominating set. Moreover, we clearly have that $$D$$ has size $$k$$ as $$\mathcal{S}'$$ has size $$k$$.