# Vertex Cover of size k in a tree?

What is a polynomial time algorithm for finding a vertex cover of size $k$ in a tree? Would depth first or breadth first search be efficient or is there some other algorithm that finds the vertex cover that takes $n^k$ time rather $2^n$ time?

• What have you tried and where did you get stuck? This is a standard problem, have you searched for solutions? – Raphael Dec 3 '14 at 18:55
• $n^k$ isn't considered efficient at all, in fact, there exist a trivial $O(n^k)$ algorithm for VC on general graphs.. – R B Dec 3 '14 at 19:06
• I used a greedy algorithm based on an adjacency list and marked either the node or its parent node depending on if it was in the base of the tree. Then, I removed n from graph G and checked the parent node to see if it had any more children, if it did not I added the parent node to L. Finally, I checked if the size of the list was k. – user24402 Dec 3 '14 at 19:08
• @RB In fact a trivial $O(2^k (n+m))$ algorithm – Pål GD Nov 9 '15 at 12:37

Hint: Suppose $x$ is a leaf and $y$ is the unique neighbor of $x$. Show that there is always a minimum vertex cover which contains $y$. (Every vertex cover contains either $x$ or $y$; if it contains $x$, then replacing $x$ with $y$ we still get a vertex cover.)