Proving a factor 2 performance guarantee for a greedy minimum cardinality vertex cover algorithm (Exercise)

Question

Exercise 1.3 from Vijay Vazirani - 'Approximation Algorithms' asks:

Consider the following factor $2$ approximation algorithm for the cardinality vertex cover problem. Find a depth first search tree in the given graph, $G$, and output the set, say S, of all the nonleaf vertices of this tree. Show that S is indeed a vertex cover for $G$ and $|S| ≤ 2$ · $OPT$. Hint: Show that $G$ has a matching of size $|S|/2$.

$EDIT$: the hint originally reads as follows: 'Show that G has a matching of size |S|'. A counterexample to this is when G is a path of length $4$ - then the DFS tree $T = D$, and a maximum matching is of size $2$. I took this to be a misprint and assumed that $|S|/2$ is the number the hint meant to refer to. Now after reading fade2black's comment, he also has a counter example in which $S$ is not a cover of $G$. After thinking about this for a while, I now cannot see for what reason $|S|$ should always be a cover of $G$. What I thought was proof of this statement (my attempt at the first part of the question below), is actually proof that $S$ is always a cover of $T$. Any ideas? Am I missing something? Is this a misprint, or is this just a poorly formulated question?

My attempt:

Showing $S$ is a vertex cover of $G$: Assume not. Then there is at least one vertex $v \in G-S$, $s.t.$ $v$ is a leaf and not adjacent to any vertex in $S$. Then either $v$ is disconnected in $G$, or $v$ is adjacent to some other leaf in $G$. If $v$ is adjacent to some other leaf in $G$, this implies that $G = K_2$, in which case $S = \emptyset$ and selecting either of the two vertices on its own gives a vertex cover. Therefore, if $G \neq K_2$ and $G$ is connected, $v$ must be connected to some $w \in S$.

Showing that $|S| \leq 2 \cdot OPT$: Consider a $2$-colouring of the vertices in $S$. At least one of the colours will have been used to colour at least half of the vertices in $S$. Pick that colour, and for each vertex coloured by it, match exactly one of its incident edges. It follows that $G$ admits a matching of size $|S|/2$. Let $M$ be a maximal matching in $G$. Then $|S|/2 \leq |M|$. We know that the minimum cardinality vertex cover of $G$ can be bounded from below by $|M|$, i.e. $|M| \leq OPT$. Together this gives $|S|/2 \leq |M| \leq OPT$, which implies that $|S|/2 \leq OPT \implies |S| \leq 2 \cdot OPT$.

Im pretty happy with the logic behind my solution to the second part of the exercise (showing that $|S| \leq 2 \cdot OPT$), but I'm not sure if the first part is quite there - I think the logic needs a bit of work. Any suggestions?

Answer 1

In this exercise, we think of the DFS tree (in fact, DFS forest) as a rooted tree (in fact, forest). We define leaf and nonleaf accordingly. In particular, the root of the tree is not a leaf vertex unless it is an isolated vertex.

In order to prove that the set of nonleaf vertices is a vertex cover, you have to notice that no edge can connect two leaves $x,y$ of the tree, since if $x$ is the vertex reached first, then $y$ will be a descendant of $x$.

Answer 2

I am writing it as an answer since it is too big for a comment.

My concern is the claim "Show that S is indeed a vertex cover for $G$". I assume the standard definition of a vertex leaf and the standard definition of a vertex cover.

Consider a cycle graph on $n$ vertices: $v_1,v_2,\dots, v_n, v_1$. This graph has a DFS tree $v_1,\dots, v_n$ which has only two leaf vertices $v_1$ and $v_n$. Then consider the set of nonleaf vertices of this tree, i.e., $\{v_2, \dots, v_{n-1}\}$. Is it a vertex cover? The edge $\langle v_n,v_1\rangle$ is not covered by this set.