Greedy algorithm for vertex cover

Question

Given a graph $G(V, E)$, consider the following algorithm:

1. Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$)
2. Let $v$ be one of the vertices with degree equal to $d$
3. Remove all vertices adjacent to $v$ and add them to the proposed vertex cover
4. Repeat from step 1. until in $G$ there are only vertices with degree $0$ (no edges in the graph)

At the end the removed vertices are a vertex cover of the given $G(V, E)$, but is it a minimum vertex cover? Is there an example where the algorithm does not find a minimum vertex cover?

Answer 1

Start with a clique on the vertices $A,B,C,D$.

Connect $A,B$ to a new vertex $a$.

Connect $B,C$ to a new vertex $c$.

Connect $a,c$ to a new vertex $b$.

The vertex $b$ is the only one of degree 2, so your algorithm will start by adding $a,c$ to the vertex cover. The remaining graph consists of the clique $A,B,C,D$ and the isolated vertex $b$, so the algorithm will add 3 more vertices, ending up with a vertex cover of size 5.

In contrast, the 4 vertices $A,B,C,b$ cover all edges.

Answer 2

Take $k$ copies of $C_4$, and attach them all to a single vertex. For instance, if $k=2$, you get the graph $X_{27}$ shown below (courtesy of graphclasses.org):

A vertex cover of size $k+1$ can be obtained by selecting the vertex with maximum degree (let's call it $w$) and all vertices that are not adjacent to it.

The algorithm you propose might start with one of the vertices of degree 2 that are not adjacent to $w$ (say, $v$) and will add both neighbours to the cover, and then we repeat the process on the rest of the graph. In the case where $k=2$ above, you will end up with a cover of size $4$, whereas what I described in the previous paragraph yields a cover of size 3.

Side note: as counter-intuitive as this algorithm seems (in the sense that if I had to be greedy with respect to the degree, I'd naturally extract a maximum degree vertex at every iteration), it seems to have been proposed before. See this question on cstheory.

Answer 3

Using the notation $[v](n_1,\ldots,n_k)$ to mean that because of vertex $v$ we remove its neighbors $n_1$ through $n_k$, your algorithm might remove vertices in the following way: $[2](1,5,7), [6](8), [3](9,11), [10](12), [4](13,15), [14](16)$. This yields a vertex cover of size $10$.

However, $(2,6,8,3,10,12,4,14,16)$ is a vertex cover of size 9.