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