# Greedy algorithm for vertex cover

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?

• I can say without checking that it doesn't always find a vertex cover (otherwise this algorithm would be found long ago). What's the motivation for your question?
– user114966
Aug 6, 2020 at 15:11
• "doesn't always find a vertex cover" -> "doesn't always find a minimum vertex cover". I personally find this question rather strange (and a bit annoying): you come up with random heuristics, and of course it won't work for an NP-hard problem. While others may feel that it's a nice exercise to find a counterexample for a specific algorithm, I don't understand why you ask this question at all, also without showing any attempt (given that it should be simple to find a counterexample).
– user114966
Aug 6, 2020 at 15:25

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.

• Why would the algorithm "add $3$ more vertices"? I see that it will add only $2$. The isolated vertex is not taken into account by the algorithm as step 1 only considers vertices with degree at least 1. Aug 6, 2020 at 16:19
• It will choose, say $A$, and add its three neighbors $B,C,D$. This is actually optimal – you need three vertices to cover all edges of the clique. Aug 6, 2020 at 20:12
• you're right, thanks! Aug 6, 2020 at 22:19

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.

• This is easily overcome by starting at all vertices of minimal degree, right? It's easy to adapt the algorithm to solve this, so I don't think it is a very strong counterexample. Aug 17, 2020 at 10:00

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.