2

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.

Let G = (V,E) be a tree with arbitrary weights associated with the vertices.

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?

enter image description here

  • 2
    Backtracking. – 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.