Error lower-bound for an algorithm for vertex cover

Question

I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:

• Fix some order $e_1, e_2, . . . , e_m$ over all edges in the edge set E of G, and set $B_0 = \emptyset$.
• Add to $B_0$ all isolated vertices, i.e. the ones without any incident edges.
• For every edge $e$ in $e_1, e_2, . . . , e_m$
  • if both endpoints of $e$ not contained in $B_0$, then
  • flip a fair coin deciding which of the endpoints to choose, and add this endpoint to $B_0$.

How can I prove that, for every constant $c \geq 1$, the algorithm might produce a $B_0$ with $|B_0 | \ge c|OPT|$?

Answer 1

Fix a star graph of $c + 1$ vertices. A star graph is a vertex connected to all other vertices in the graph (a universal vertex called the center), and all other vertices are pairwise not adjacent. Here is a visual example. $c$ is the center of the star.

Now an optimal solution is to pack the center of the star. The size of this solution is equal to 1. For each edge, suppose our algorithm packs the other end of the edge (the non-universal vertex), then we need to pack all vertices of the graph except for the center and hence, we need to pack $c$ different vertices. In total we get $|B_0| = C |OPT|$ for any arbitrary but fixed value of $c$.

---

Note A simple modification of the algorithm yields a derandomized approximation algorithm with answer size at most twice as large as the optimum. It goes as follows: if both endpoints of the edge are not in $B_0$, then add both endpoints to $B_0$ and iterate.

The reason why this works is simple. The edges, who get their endpoints added for a maximal matching and hence, we add twice the number of vertices in a maximal matching to the cover. Note that the size of a matching in a graph is a lower-bound on the size of a minimum vertex cover and hence, we add at most twice many vertices as the size of the minimum vertex cover.