Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
It's called a "minimum weighted dominating set". –  Douglas S. Stones Aug 12 '12 at 23:06

1 Answer 1

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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