World's most popular travel blog for travel bloggers.

[Solved]: Why is Savage's Vertex Cover algorithm a 2-approximation?

, , No Comments
Problem Detail: 

Carla. D. Savage formulated the following approximation algorithm for the vertex cover problem.

Given graph $G$, start at arbitrary node and traverse $G$ depth-first

Obtain DFS tree $T$

return $V_C =$ internal nodes of $T$.

Now I read everywhere that this algorithm is supposed to yield a 2-approximation, but the only proof I found was here, and frankly, I don't get it and it's rather longish. Unfortunately also, the original paper is nowhere to be found. At other places where this was given as an exercise, I find the hint that one should first show that the tree $T$ admits a matching $|M| \ge \frac{1}{2} |V_C|$. But if I had proved that (which I have no clue how to do), I have no idea how to use that knowledge. I don't see how I can put bounds on the output of the algorithm without an estimate for the number of internal nodes of an arbitrary tree. And the way I see it, such a tree can have between $1$ and $n-1$ leaves (consider the graphs which are a chain, or a star, respectively).

So I am puzzled. How could one show that this is a 2-approximation?

Asked By : oarfish

Answered By : Yuval Filmus

First of all, you have to show that $V_C$ is a vertex cover. This is because any edge touching a leaf also touches an internal node.

Next, we show that the DFS tree has a matching of size at least $|V_C|/2$. Since each vertex cover must contain at least one vertex from each edge in the matching (since any one vertex covers only one edge from the matching), this shows that the minimum vertex cover has size at least $|V_C|/2$, so we get a 2-approximation algorithm.

It remains to show that any tree $T$ has a matching of size at least $I(T)/2$, where $I(T)$ is the number of internal node. The proof is by induction on $|T|$. If $T$ contains one vertex then $I(T)=0$ and so there is nothing to prove. Now suppose that the tree contains a root $r$ and subtrees $T_1,\ldots,T_n$. Let $r_1$ be the root of $T_1$, and let $S_1,\ldots,S_m$ be the subtrees of $T_1$. The matching we are going to construct consists of matchings in $S_1,\ldots,S_m,T_2,\ldots,T_n$ together with the edge $(r,r_1)$ (you can check that this is indeed a matching). This matching contains at least $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2$ many edges. We obtained the forest $S_1,\ldots,S_m,T_2,\ldots,T_n$ by removing two vertices $r,r_1$, so $I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n) = I(T)-2$. This completes the proof since $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2 = 1+(I(T)-2)/2 = I(T)/2$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback