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
    I've discovered that this is the problem of a dominating set. Which does help2011-11-10
  • 0
    I take your comment to indicate that you've found the answer to your question. In that case, please either answer it yourself and accept the answer (which is not only allowed but [encouraged](http://blog.stackoverflow.com/2011/07/its-ok-to-ask-and-answer-your-own-questions/)), or if you don't want to spend time writing it up, delete the question. Otherwise the question will keep floating around as unanswered.2011-11-10
  • 0
    Answered, but since my rep is low, couldn't properly answer it. I edited it into my original question.2011-11-10
  • 0
    Thanks. 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.2011-11-10

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.