2
$\begingroup$

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

Any useful links or suggestions would be really helpful. Thanks in advance! Seb

  • 0
    It's called a "minimum weighted [dominating set](http://en.wikipedia.org/wiki/Dominating_set)".2012-08-12

1 Answers 1

3

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

  • 0
    Wow. Thanks people. I guess I've got a lot of reading to do.2012-08-17