# Vertex Cover approximation algorithm

I have an algorithm that solves the Vertex Cover problem. The algorithm is

Repeat while there is an edge:

Arbitrarily pick an uncovered edge $$e = uv$$ and add $$u$$ and $$v$$ to the solution. Delete $$u$$ and $$v$$ from the graph.

I know this strategy is a 2-approximation to Vertex Cover and that its worst example is the complete bipartite graph $$K_{n,n}$$. In this graph, the algorithm will return a vertex cover of size $$2n$$ whereas the optimal solution is of size $$n$$.

Question: Does there exist a graph with Minimum Vertex Cover of size 10 where this strategy finds a minimum vertex cover?

• The performance you mention on complete bipartite graphs is at odds with the stated approximation ratio. – Yuval Filmus Dec 21 '18 at 19:13
• A good example for this algorithm is a matching. – Yuval Filmus Dec 21 '18 at 19:13
• ohhh can you give any worst case example? – Null Pointer Dec 21 '18 at 19:20
• @YuvalFilmus If I understand the question as well as your suggestion, your suggestion ($10K_2$) gives a worst case, and not a best case. It seems that OP is looking for examples where the approximation algorithms actually gives the optimum. – Pål GD Dec 22 '18 at 12:40

• Also known as $5K_3$. – Pål GD Dec 22 '18 at 12:41