Approximating maximal independent set with a minimal vertex cover approximation

Question

The minimal vertex cover problem has a 2-approximation algorithm.

We can reduce the maximal independent set problem to the minimal vertex cover problem as shown here.

Does this mean that I can use the $2$-approximation for minimal vertex cover to get a $1/2$-approximation for maximal independent set?

My approach:

// is this a 1/2-approximation algorithm?
approxAlgForMaxIS(Graph G) {
    minVC = computeMinVC(G);
    maxIS = G.V - minVC;   // remove all vertices in the minVC from G
    return maxIS
}

Answer 1

No, unfortunately this doesn't work. Denote by $\newcommand{\VC}{\mathrm{VC}}\VC$ the size of a minimum vertex cover and by $\newcommand{\IS}{\mathrm{IS}}\IS$ the size of a maximum independent set, so that $\VC+\IS=n$. The approximation algorithm for $\VC$ produces a vertex cover $C$ whose size satisfies $|C| \leq 2\VC$. The complement of $C$ is an independent set $I$ whose size satisfies $$ |I| = n-|C| \geq n-2\VC. $$ Unfortunately, $n-2\VC$ can be much smaller than $n-\VC$, and there's no constant lower bound on the ratio $$ \frac{n-2\VC}{n-\VC}. $$

As an example, let's see how the algorithm which picks a maximal matching fares on a graph consisting of a matching on $n$ vertices. The minimum vertex cover has size $n/2$, and so the maximum independent set has size $n/2$. The maximal matching algorithm picks all edges in the graph and then all vertices contained in them – in other words, it picks all vertices. It thus gives a vertex cover of size $n$, which corresponds to an independent set of size 0.

This difference between vertex cover and independent set is reflected in the fact that it is NP-hard to approximate independent set to within $n^{1-\epsilon}$, for any $\epsilon > 0$.