0
$\begingroup$

I'm having a hard time figuring out how to reduce a problem to prove that it is NP-complete.

Basically, my problem is this:

Given an undirected graph, find a set $S$ such that for all nodes in $G \setminus S$ (i.e. all other nodes), there exists at least one edge from each node in $G \setminus S$ to a node in $S$. Expanding on this, I want to know if I can find this particular set with size at most equal to some integer $k$.

  • 0
    Th$a$nks. I moved it to a community wiki answer, and I see you've already accepted it. The effect is the same, reputation-wise, since neither community wiki answers nor self-answers generate points.2019-04-19

1 Answers 1

4

A dominating set is simply a subset $S$ of $V$ such that each member of $V \setminus S$ contains at least one edge to a member of $S$.

We reduce vertex-cover to dominating set in the following way:

Create a new graph such that there exists a vertex for each vertex in G. Furthermore, add a new vertex for each edge in $G$, such that there now exists a triangle of edges. That is to say, for an edge, $e$ = ($u, v$) there now exists a new vertex, $z$, and the edges ($u, v$), ($u, z$), ($v, z$).

We have to prove that our graph $G$ has a vertex cover of size $k$ iff the new graph has a dominating set of size $k$. If we have a set, $S$, that is a vertex cover of $G$, then we know that the same set is a dominating set on the new graph. By definition of vertex cover, each edge in $G$ is incident to at least one vertex in $S$. Therefore, each triangle of vertices in the new graph has at least one member of which belongs to $S$. As a result, we know that each vertex in the new graph is either in $S$ or adjacent to $S$, which is the definition of a dominating set.