# Maximum Vertex Cover

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.

• 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? – Nick Peterson Jul 4 '13 at 13:51
• 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. – user2549925 Jul 4 '13 at 14:33
• Also posted at stackoverflow.com/users/2549925/user2549925 – Falk Hüffner Jul 4 '13 at 15:34
• Maybe you are looking for the minimum weighted vertex cover problem? – 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.) 