2
$\begingroup$

I am studying the book "Parametrized Algorithms" and it suggests a bounded search tree algorithm for k-Vertex Cover. Basically we look at a vertex v and say :
Either v will cover it's incident edges or it has to be it's neighbors $N(V)$ so either $v$ or $N(v)$ will end up in the cover.
That's 2 choices , we build a tree with these . The total running time is summarized by this relation :
$T(k) =T(k-1) + T(k-N(v)) + O(n)$
Considering the interesting case is $N(v) \geq 2$ then $k - N(v) \leq k-2$ so we get: $$T(k) =T(k-1) + T(k-2) + O(n)$$ Now the book says that "Vertex Cover can be solved optimally in polynomial time when the maximum degree of a graph is at most 2".
"Thus, we branch only on the vertices of degree at least 3, which immediately brings us to the following upper bound on the number of leaves in a search tree:" enter image description here

Since the are no vertices with degree 3 or more how do we branch on these ? What am I missing here?

$\endgroup$
1
  • $\begingroup$ why the first two recursive formulae include an O(n)? $\endgroup$
    – Mengfan Ma
    Jul 18 at 15:53

1 Answer 1

1
$\begingroup$

Once all vertices have degree $<=2$ you don't branch on them - you just apply a standard polynomial time algorithm to solve it.

Since your graph consists of a disjoint set of cycles and line graphs, the min vertex cover for components which are line graphs would be $⌊C/2⌋$ and $⌈C/2⌉$ for cycles where $C$ is the size of the component. Therefore this can be solved in $O(n+m)$ as the problem just reduces to finding the size of components within a graph.

The recurrence given is for reducing the graph to a form where all vertices have degree $<=2$ as you either remove the current vertex or remove 3 of its neighbours. Doing this repeatedly will eventually lead you to a graph where all vertices have degree $<=2$

$\endgroup$
2
  • $\begingroup$ "you either remove the current vertex or remove 3 of its neighbors" should be "you either remove the vertex or remove all of its neighbors". $\endgroup$
    – Mengfan Ma
    Jul 18 at 16:33
  • $\begingroup$ Also, "doing this repeatedly will eventually lead you to a graph where all vertices have degree <= 2" should be "doing this repeatedly will eventually lead you to a graph where all vertices have degree <= 2 or a k-vertex cover problem with k <=2" $\endgroup$
    – Mengfan Ma
    Jul 18 at 18:13

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.