1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Oct 29 '17 at 15:58
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – swingballchamp42 Feb 28 '18 at 9:40
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – swingballchamp42 Oct 29 '17 at 17:56
  • $\begingroup$ Agree. There is something wrong with the problem statement. $\endgroup$ – fade2black Oct 29 '17 at 18:00
  • $\begingroup$ I noticed $S$ is always a dominating set. But then the analysis for the second part of the question no longer works. $\endgroup$ – swingballchamp42 Oct 29 '17 at 20:40
  • $\begingroup$ 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. $\endgroup$ – fade2black Oct 29 '17 at 20:54
  • $\begingroup$ 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. $\endgroup$ – fade2black Oct 31 '17 at 12:09

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.