0
$\begingroup$

You are given a tree T where every node i has weight wi ≥ 0. Design a polynomial time algorithm to find the weight of the smallest vertex cover in T. For example, suppose in the following picture wa = 3, wb = 1, wc = 4, wd = 3, we = 6. Then, the minimum cost vertex cover has nodes a, b with weight 3 + 1 = 4.

enter image description here

In the question, the opt i am chosing is OPT(v,boolean) is a min weight vertex cover for subtree v and boolean means whether it contains v or not. What are the subproblems that are formed and how do I move ahead? any hint is helpful.

$\endgroup$
0
$\begingroup$

I'll assume the tree has been rooted arbitrarily.

Taking y our idea we let $OPT(v, 1)$ to be equal to the minimum weight of a vertex cover of the subtree rooted in $v$ that includes $v$, and $OPT(v, 0)$ the one where $v$ is not included.

$OPT(v,1)$ means you the weight of that cover includes $w(v)$ and also that we have already dealt with edges that touch $v$, so all you need are MWVC for each of the subtrees of its children. So for each children $u$ of $v$, you take the minimum between $OPT(u,0)$ and $OPT(u,1)$, and you add that to $OPT(v,1)$. This can be done bottom-up.

$OPT(v,0)$ means you need to select every children $u$ of $v$, as otherwise the edge $uv$ wouldn't be covered. Thus, for every child $u$, you add $OPT(u,1)$ to $OPT(v,0)$.

I'm sure this is enough for you to code it!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ For the case when OPT(v,0) do all the children of v need to be in the cover? How can any child not be in the cover? if any child is not in the cover then it means v and child u are not in cover and the edge v-u is not covered right? $\endgroup$ – rspenpal May 24 at 15:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.