Vertex Cover for Trees

A set of nodes where every edge is adjacent to at least one of the nodes.

Dynamic Programming Solution

Dynamic Programming

Optimal substructure

Consider the subproblems:

1. - the size of the vertex cover, if it is uncovered.
2. - the size of the vertex cover, if it is covered.

Solving subproblems

Given is a child of , consider:

1. Since is not covered, would have to be covered, thus:
2. Since is covered, we can just take the minimum of the vertex covers of :