# Minimum Weighted Vertex Cover, Dynamic Programming

So my solution in my mind right now:

Let $$OPT(n, boolean)$$ be the minimum vertex cover rooted at vertex n that includes that vertex if boolean is true, false otherwise.

So my idea is:

If a vertex is not included, any edges leading away from it, their vertices are to be part of the vertex cover. $$OPT(n, F) = OPT(n.left, T) + OPT(n.right, T)$$

If a vertex is included, it can or can not be included, the vertex at the other end of an edge. $$OPT(n, T) = min\{OPT(n.left, T) + OPT(n.right, T), OPT(n.left, F) + OPT(n.right, F), OPT(n.left, F) + OPT(n.right, T), OPT(n.left, T) + OPT(n.right, F)\} + n.weight$$

Then we can solve this problem with $$min\{OPT(root, T), OPT(root, F)\}$$

Is this the right idea? Is there anything I might be missing? If so, what would be the correct approach?