Given a graph G=(V,E) and a positive weight function w on all the vertices, find a subset C from V such that all the edges (u,v) in E, at least one , u or v is contained in C and sum of all the weights of vertices in the set C is maximized.

For the Minimum Vertex Cover Problem, I used grMinVerCover (by calling grMinVerCover (E,w) ) function in Matlab. But I could not find a Maximum Vertex Cover function.

So, I calculated the reciprocal of the weights (w') of vertices in w, and then applied the vertex cover to E and w' by calling grMinVerCover(E,w'). The answers I am getting are correct but I want to know if this is logically correct?

Basically i need to find a Cover such that the number of vertices is minimized and the total weight is maximised.

  • 1
    $\begingroup$ There needs to be more conditions on it than you've given - otherwise, doesn't choosing $C=V$ give you the best possible weight every time? $\endgroup$ – Nick Peterson Jul 4 '13 at 13:51
  • $\begingroup$ The problem requires that we create a set C which contains the minimum number of vertexes such that : 1)each edge (u,v) in E has at least one vertex u or v belonging to C. 2)And that the total weight of that set of vertices be maximum. These are the two conditions that define the problem. $\endgroup$ – user2549925 Jul 4 '13 at 14:33
  • $\begingroup$ Also posted at stackoverflow.com/users/2549925/user2549925 $\endgroup$ – Falk Hüffner Jul 4 '13 at 15:34
  • $\begingroup$ Maybe you are looking for the minimum weighted vertex cover problem? $\endgroup$ – xuhdev Mar 6 '17 at 9:43

As mentioned in the comments your reasoning is not true, since the maximum vertex cover is always the complete vertex set. The statement is also false if you consider the maximum minimal vertex cover. (You take all vertex covers that are not vertex covers after removing an arbitrary vertex from the cover, and then pick the maximal vertex cover of these covers.) enter image description here

  • $\begingroup$ Ok.Let me simplify my problem a little more. I have a set of vertices and each carry a score associated with them. The higher the score, the better they rank. (if one sentence has a high score, it will have a lower rank for eg. rank 1). Now given a graph (V,E); I would like to cover all these edges using only the better ranked vertices. Hence, I am using minimum vertex cover to cover all these edges but also include the better ranked vertices in doing so. Is this wrong? And if it is, is there something else that I should be using instead of Minimum Vertex Cover? $\endgroup$ – user2549925 Jul 5 '13 at 3:01
  • $\begingroup$ It is not clear to me what "using only the better ranked vertices" means. Perhaps you want to find an inclusion-minimal vertex cover (that is, one that does not contain redundant vertices that could be removed while still being a vertex cover) that has maximum weight? Maybe you should edit your question and add some nontrivial examples. $\endgroup$ – Falk Hüffner Jul 5 '13 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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