How can you find the vertex cover of a graph in linear time if the graph is a tree?

Question

Algorithms

Hello. Tell me, who knows how the problem indicated in the title is solved, or at least with the help of what standard methods it can be solved. Thank you.

Answer 1

Recursion.
For each subtree, we look for two covers: P is the minimum cover in general, and Q is the minimum cover containing the root. Let T be our tree, X be its subtrees growing from the children of the root. Then
Q(T)=1+sum(P(X))
(the root is included, all edges going to it are taken into account, any coverings can be chosen in subtrees)
P(T)=min(Q(T),sum(Q (X)))
(either the root is not included - and one must take covers of subtrees containing roots, or take the already constructed cover Q).
For leaves P=0, Q=1.