1
$\begingroup$

This question already has an answer here:

I have a problem where I'm given the input of a graph. The output would be a set of vertices such that I have the minimum number of vertices to cover other vertices and if there is more than one option then then I'd have to choose the maximum weighted vertex set. I'm trying to approach this in a Dynamic programming though I've always come at a dead end. I'm trying to maximize the number of vertices weights yet at the same time Im trying to minimize the number of vertices selected.

enter image description here

In this case the potential answers can be

{A,B} = 10

{A,C} = 9

{C,D} = 9

{D,B} = 10

Since {D,B} and {A,B} have equal weights then either is a correct solution.

I'm pretty confident that I should be memorizing the weights sum though everything else I've tried led to a dead end. Can anyone provide insights?

This is not a vertex cover problem.

enter image description here

To be honest Im not really sure what my recurrence relation is. I tried thinking about the problem in such a way that I already have a an optimal solution of a graph G and I want to add more more vertex. The problem is I can add another vertex that may have a lower weight than what the G has in optimal solution, but this new vertex covers all other vertices so I'd have to choose it anyway. The "maximization" constraint fails with respect to previous input as I'm now tackling the other constraint on the problem.

$\endgroup$

marked as duplicate by D.W., Raphael Jun 6 '15 at 7:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ en.wikipedia.org/wiki/Vertex_cover $\endgroup$ – D.W. Jun 6 '15 at 2:11
  • $\begingroup$ What @D.W. is saying is that this is a (variant of) a famous problem that is thought to be hard to solve, that is we don't know efficient algorithms (in the general case). If you search for "Vertex Cover" and the terms from here, I'm sure you'll find something helpful. (In case you don't, please edit your question to include why none of the approaches helps you.) $\endgroup$ – Raphael Jun 6 '15 at 7:16
  • $\begingroup$ Regarding your approach, whenever you want to propose a dynamic programming solution, the first step is to set up a recurrence equation. Can you do this here? $\endgroup$ – Raphael Jun 6 '15 at 7:18
  • $\begingroup$ Question edited. This is not a vertex cover. $\endgroup$ – RandomGuy Jun 6 '15 at 11:06
  • 1
    $\begingroup$ It's not vertex cover but dominating set, which is also NP-complete. $\endgroup$ – David Richerby Jun 6 '15 at 11:41