# Vertex Cover Reduction

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

-

I've discovered that this is the problem of a dominating set. Which does help – CCSab Nov 10 '11 at 3:00
– joriki Nov 10 '11 at 9:24
Answered, but since my rep is low, couldn't properly answer it. I edited it into my original question. – CCSab Nov 10 '11 at 9:40
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. – joriki Nov 10 '11 at 9:49

## 1 Answer

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 edge in the new graph is either in $S$ or adjacent to $S$, which is the definition of a dominating set.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 26, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9576338529586792, "perplexity_flag": "head"}