As we have seen before, finding the minimum vertex cover of a graph is NP-complete. However, a very simple procedure can efficiently find a cover that is at most twice as large as the optimal cover:
VertexCover(G=(V,E))
while do:
Select an arbitrary edge
Add both u and v to the vertex cover
Delete all edges from E that are incident on either u or v.
It should be apparent that this procedure always produces a vertex cover, since each edge is only deleted immediately after an incident vertex has been added to the cover. More interesting is the claim that any vertex cover must use at least half as many vertices as this one. Why? Consider just the edges selected by the algorithm. No two of these edges can share a vertex. Therefore, any cover of just these edges must include at least one vertex per edge, which makes it at least half the size of the greedy cover.
There are several interesting things to notice about this algorithm:
Figure: Neglecting to pick the center vertex leads to a terrible vertex cover
The important property of approximation algorithms is relating the size of the solution produced directly to a lower bound on the optimal solution. Instead of thinking about how well we might do, we have to think about the worst case i.e. how badly we might perform.