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

  • $\begingroup$ I've discovered that this is the problem of a dominating set. Which does help $\endgroup$ – CCSab Nov 10 '11 at 3:00
  • $\begingroup$ 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), or if you don't want to spend time writing it up, delete the question. Otherwise the question will keep floating around as unanswered. $\endgroup$ – joriki Nov 10 '11 at 9:24
  • $\begingroup$ Answered, but since my rep is low, couldn't properly answer it. I edited it into my original question. $\endgroup$ – CCSab Nov 10 '11 at 9:40
  • $\begingroup$ 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. $\endgroup$ – joriki Nov 10 '11 at 9:49

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.

  • $\begingroup$ What if we have vertices of degree 0 in G? Clearly, if you copy them to the transformed graph, the reduction will break because these vertices are not adjacent to any other vertex. $\endgroup$ – LanceHAOH Nov 24 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.