= Maximum independent set in a tree
{title2=$I(v)=1+\sum_w O(w),\quad O(v)=\sum_w\max(I(w),O(w))$}
Root a finite <tree>. The two <dynamic programming> states are the optimal size in the descendant subtree when its root $v$ is included, $I(v)$, or excluded, $O(v)$. The sums run over its children. Inclusion forces every child to be excluded; exclusion permits each child's better state. Child subtrees have no edges between them, which proves independence of these choices. The leaf states are $I=1,O=0$, and the root's better state gives the optimum.
A <postorder traversal> computes the states in $O(n)$ time and storage. Reconstruct a set by following an attaining root choice and the same child constraints, breaking ties arbitrarily. The empty and singleton cases use the ordinary non-strict <subset> convention.
Back to article page
