2
$\begingroup$

The maximum weighted independent set for a tree can found out using the following dynamic programming approach.

Min[u] = wt(u) + Σ Mout[v] where v ∈ children(u) Mout[u] = Σ max { Min[v], Mout[v] } where v ∈ children(u)

where Min[u] and Mout[u] computes the total weight of the maximum independent set for the sub tree rooted at u by including or excluding u respectively.

I tried to proof the correctness of this algorithm. Suppose the independent set ( say I ) generated from this algorithm is not of maximum weight. Let the maximum weighted independent be I'. Then there must be a vertex V'∈ I' and V' ∉ I. And also there can be 2 cases. Either parent(V')∈ I or parent(V') ∉ I. I tried both the cases to solve furthur but could not proceed. Is this approach correct or there is some alternative way to prove the correctness.

$\endgroup$
1
$\begingroup$

Here is an easier-to-understand dynamic programming approach. I think if you can prove this, then you can prove yours.

Let $\textsf{I}(u)$ be the weight of the weighted largest independent set of subtree rooted at $u$.

The goal is to compute $\textsf{I}(r)$, where $r$ is the root of the tree.

The recurrence relation for dynamic programming is:

$$\textsf{I}(u) = \max \{ w(u) + \sum_{v: \text{ grandchild of } u} I(v), \sum_{v: \text{ child of } u} I(v) \}$$

Can you prove (or disprove) it?

Hint: Do a simple case-by-case analysis.

$\endgroup$
  • $\begingroup$ So do I have to consider the cases like: w(u) > Σ w(v) where v ∈ children(u) and corresponding cases for grand children as well. Also say v1 is the child of u. Then I(v1) may be calculated including v1 or excluding it. If all such v1 of u are excluded then we can easily add u to the set I(u). But if v1 is included in I(v1) then the whole sub tree under v1 has to be changed to include u as it may violate independence set property. Can you elaborate on some of the cases? $\endgroup$ – Aniket Apr 25 '15 at 13:23
  • $\begingroup$ @Aniket If $r$ is in the solution, all its direct children (say, $v$) cannot be in (That is your first equation). When $v$ is not in the solution, each of its direct children may (because $v$ is not in, so the existence of its child in the solution does not violate the independent set property) or may not be in the solution (that is $\max$ part in the your equation). $\endgroup$ – hengxin Apr 25 '15 at 13:55

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.