How to find the minimum vertex cover of a graph ?

general
,
1

I am trying to solve this problem http://www.spoj.com/problems/PT07X/ understood the question but

unable to figure out an algorithm.Any one help me in solving the problem.

2

There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal.

  1. For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover).
  2. For each internal node:if any of its children is not selected, then select this node.DFS call at each child can be used to check this.