Prove that the greedy algorithm for the minimum edge cover problem is 2-approximation

Question

As said, I had to prove that the greedy algorithm:

1. Initialize $C = ∅$
2. Look for an un-covered vertex and add one of its edges to $C$
3. Repeat 2 while there's uncovered vertices

Is a 2-approximation algorithm.

My take was:

Let's say that $OPT$ (the optimal solution) takes $k$ edges, we should prove that $ALG$ takes at most $2k$ edges.

Let's assume by contradiction that $C=2k+1$. That means that $ALG$ covers at least $2k+1$ vertices, because each edge chosen by $ALG$ covers at least one vertex. We get that $OPT$ covers at most $2k$ vertices but $ALG$ covers at least $2k+1$ which is a contradiction $⇒ C ≤ 2k$

Now that we proved that if $OPT=k$ we get that $ALG ≤2k$ we can easily show that $\frac{ALG} {OPT}≤ 2$

Is my proof correct?

Answer 1

No. Your proof would be "correct" for any constant, not only $2$ (which is a clear big red alert!).

The actual proof is as follows:

Let $OPT$ be the optimal solution, and $ALG$ the solution from this algorithm. Notice that each edge in $OPT$ connects two vertices, and thus each such edge must contribute to the covering with at most 2 vertices. Hence, the number of vertices in the graph is at most $2k$ where $k$ is the number of edges in $OPT$. Since your algorithm will take an edge for every node at the worst case, the number of edges in $ALG$ must be at most $2k$. Hence, $|ALG|\le 2\cdot |OPT|$, which means that the algorithm is indeed a 2-approximation of the problem.