1
$\begingroup$

pseudocode:

void recursive('k'){ // 'k' and 'i' vertices
  sumA = 0;
  sumB = 0;
  for each non visited 'i' neighbor do{
     recursive('i');
     sumA = sumA + b['i'];
     sumB = sumB + max(a['i'], b['i']);
     }
  a['k'] = 1 + sumA;
  b['k'] = sumB;
  }


void main(){
 a = b = 0; //initialize tables with 0 (zeros)
 recursive('X');  //let 'X' be an arbitrary root
 cout<

need proof that max(a['X'], b['X']) is the cardinal of the maximum independent set in the tree. What am I missing ?

Thank you in advance.

1 Answers 1

2

The element $a[i]$ is the size of the maximal independent set in the subtree rooted in $i$ which contains $i$.

The element $b[i]$ is the size of the maximal independent set in the subtree rooted in $i$ which doesn't contain $i$.

The algorithm computes these recursively, and then choose the maximal of the two at the root.

  • 0
    are you suggesting that this would be enough to say in order to prove that it's the maximal ?2010-10-31
  • 0
    You have to prove that the algorithm calculates both arrays correctly, but that's not difficult.2010-10-31