0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ What have you tried and where did you get stuck? This is a standard problem, have you searched for solutions? $\endgroup$ – Raphael Dec 3 '14 at 18:55
  • 2
    $\begingroup$ $n^k$ isn't considered efficient at all, in fact, there exist a trivial $O(n^k)$ algorithm for VC on general graphs.. $\endgroup$ – R B Dec 3 '14 at 19:06
  • $\begingroup$ 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. $\endgroup$ – user24402 Dec 3 '14 at 19:08
  • $\begingroup$ @RB In fact a trivial $O(2^k (n+m))$ algorithm $\endgroup$ – Pål GD Nov 9 '15 at 12:37
1
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.