Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 6 / e

Choose a root. For each vertex $v$, define $I(v)$ as the maximum size in its descendant subtree when $v$ is included, and $O(v)$ as that size when $v$ is excluded. For its children $w$,A leaf has $I=1,O=0$. If $v$ is included, all its children must be excluded. If $v$ is excluded, either child state is allowed. Different child subtrees have no edges between them because the graph is a tree, so their contributions can be optimized independently. This proves the recurrence by structural induction.

Evaluate the two states in postorder traversal. At root $r$, the answer is $\max \{I(r),O(r)\}$. For reconstruction, pick an attaining root state; an included vertex forces every child to its excluded state, while an excluded vertex permits each child to choose its larger state. Record the included vertices during this second traversal, breaking ties consistently.

With adjacency lists, rooting, state evaluation and reconstruction each take $O(|V|+|E|)=O(n)$ time, with $O(n)$ stored states and output. This is maximum independent set in a tree.

The source describes an independent set as a proper subset. For a tree with at least one edge, every independent set is automatically proper, so the algorithm meets that convention. If it is enforced literally for the single-vertex tree, return the empty set of size zero there; the usual non-strict subset convention would instead return its one vertex.