2

I'm trying to work on this problem... Below mentioned is one algorithm..i figured out..

Input a graph select a vertex with highest degree of matching with all the other nodes. Remove the edges that are incident on this node. Add the selected vertex and its edge to a set X. Return X

Where X returns the minimum set of vertices that are required for a vertex cover.Is this way correct...? Thanks

sam
  • 83
  • 1
  • 9

1 Answers1

4

To select a vertex with highest degree can't guarantee to give the best solution. For example, you have a tree with 7 vertices, edges are listed as follows:

1 2 // (1,2) is connected.
1 3
1 4
2 5
3 6
4 7

The minimum vertex cover is {2,3,4}, however, based on you greedy approach, you will choose {1} first, then you will choose at least 3 vertices to covered the left 3 edges.

Indeed, there is a greedy algorithm to solve the vertex cover problem for a tree, that is you find a leaf at each step (since the input is a tree, you can always find such leaf unless there is no edge left), then select the neighbor of the leaf to the vertex cover set X. Return X as the minimum vertex cover when the graph is empty. The complexity is O(E) when E = V-1 so that we can say it is a linear solution.

notbad
  • 2,797
  • 3
  • 23
  • 34
  • But why can you say it's optimal? – Hugo Oshiro Nov 23 '16 at 11:26
  • 2
    Say v2 is a leaf and it is connected with v1. If you want to cover the edge {v1, v2}, you can two choices while choosing v1 is always better than choosing v2 because v1 may cover more edges except {v1, v2} – notbad Nov 23 '16 at 18:52