# How to find minimum weighted vertex cover of a tree, and confused about a solution

Studying for my algorithms test by spamming Algorithm Design Manual exercises, but I'm stuck on this one. I know I have to keep score somehow.

### Give an efficient algorithm to find a minimum-weight vertix cover of `G`.

Some of my thoughts:

1. The leaf's parents (lets call it p) should be picked because they are usually more efficient. Then mark all p.parents to be "covered". Then you are left with a smaller tree. But there are counter examples to this, since it's weighted. This is only true for unweighted graphs.

Also, I am confused about part 3. of this solution given by Skiena. Could someone explain this to me? And also part 4., what does "backtracking" the score mean?

• – User Nov 3 '14 at 20:10
• Minimum Vertex cover is in NP. Intuiting an efficient algorithm to solve a variant is likely non-trivial. Library time is perhaps a better investment. – ben rudgers Nov 4 '14 at 4:48
• @benrudgers: it is only NP for general graphs. This may no longer hold true once you pose restrictions on this generality, say, by only looking at trees. – Frank Nov 4 '14 at 6:24
• @Frank Exactly. The difference between the general case and a tree is the sort of thing efficiently discovered indirectly in the library not directly via inductive proof. – ben rudgers Nov 4 '14 at 13:25
• I don't know whether you are still interested in the answer, the backtracking is simply revisiting all the vertices after the root score is computed. – xuhdev Jun 18 '15 at 22:09