# Coloring of graph such that every vertex in graph is either colored or shares an edge with a colored vertex

I'm a bit of a graph theory noob, so please forgive the absence of mathematical rigor in my question.

Here it is:

Given a graph $G \to (V,E)$, (where every vertex $v$ in $G$ has some weight $w$ associated to it), I am seeking an efficient algorithm that will find a subset $V'$ of the graph with the least total weight such that every vertex $v$ in $G$ satisfies at least one of the following conditions:

1. $v$ is in $V'$
2. $v$ shares at least one edge with some vertex in $V'$

-
It's called a "minimum weighted dominating set". – Douglas S. Stones Aug 12 '12 at 23:06

This is not a vertex cover problem. A vertex cover is a subset of the vertices such that each edge is incident to a vertex in the subset.
A reduction from set cover to the given problem can be shown in order to prove that this problem is also NP-complete.
Given an input for set cover: Create a vertex for each element with high enough price (for example, the sum of set prices + 1). Create a vertex for each set with the set price. Connect each set vertex to its' element vertices. Create a special vertex which is connected to every set vertex and has 0-price.

Edit: As Douglas S. Stones mentioned, this problem is called minimum weighted dominating set (it slipped my mind, but you've earned a proof that it is NP-complete as a result).

-
Wow. Thanks people. I guess I've got a lot of reading to do. – user37769 Aug 17 '12 at 2:15