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

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?

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Also, the reference has to go into the question body. Thank you! – Raphael Oct 29 '17 at 15:58

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

• Thanks for clearing things up. I actually managed to solve this exercise a while ago, after a colleague pointed out the fact that the root is not considered a leaf. My proof involved exactly the fact you mention in your answer. I have accepted it. – swingballchamp42 Feb 28 '18 at 9:40

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.

• I agree - you present a simple counter example, so I suppose it must be an error in the question/printing. I've added a few more details to my original post - the hint in the question also appeared to a contain an error, for which I had originally found a counter example, and I have explained this there. – swingballchamp42 Oct 29 '17 at 17:56
• Agree. There is something wrong with the problem statement. – fade2black Oct 29 '17 at 18:00
• I noticed $S$ is always a dominating set. But then the analysis for the second part of the question no longer works. – swingballchamp42 Oct 29 '17 at 20:40
• I think the claim "S is indeed a vertex cover for G " is not always true as I showed in my example, and so there is a mistake in this problem statement. In this case there is no point in proving something. – fade2black Oct 29 '17 at 20:54
• As far as I know a leaf is defined as node of degree one. We can also consider rooted trees, what you mean I guess. It write "The root is an external vertex if it has precisely one child. A leaf is different from the root", but it also writes "an external vertex (or outer vertex, terminal vertex or leaf) is a vertex of degree 1", so in the example the with the cycle graph we can still deduce that both $v-1$ and $v_{n-1}$ are leaf nodes. – fade2black Oct 31 '17 at 12:09