= Minimum vertex cover of a tree
{title2=$D_0(v)=\sum_uD_1(u),\quad D_1(v)=1+\sum_u\min(D_0(u),D_1(u))$}
Root a finite <tree>, and let $D_0,D_1$ be the optimum <vertex cover> sizes of a descendant <subtree> conditional on excluding or including its root. Excluding a parent forces all children to be included; including it permits either child state. These facts prove the displayed recurrences by <structural induction>. Empty child sums give $D_0=0,D_1=1$ at a <leaf of a rooted tree>. Evaluating in <postorder traversal> and taking the smaller root state gives a linear-time <dynamic programming> algorithm.
Back to article page
