Why is Savage's Vertex Cover algorithm a 2-approximation?

Question

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?

Answer 1

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

Answer 2

Another way to show that a vertex cover of a tree has to have at least $|V_C|/2$ nodes is the following: The tree consists of $k$ leaves and $|V_C|$ inner vertices, which have degree $\geq 2$. The degrees of the tree sum up to $2 (|V_C| + k - 1)$. Therefore we can conclude that there are $k-2$ "free" degrees we can distribute to the inner vertices (in addition to the degree of 2 that every inner vertex has to have).

So let $M$ be a set of vertices with $|M| < |V_C|/2$. Then we can get at most $2 |M| + k - 2 < |V_C| + k - 2$ degrees (summed up). But we need to have at least $|V_C| + k - 1$ to be able to cover all $|V_C| + k - 1$ edges. Therefore M is no vertex cover.