# Approximating maximal independent set with a minimal vertex cover approximation

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
}

• The way to tell whether this works is to try to prove it works! It sounds like you have an algorithm in mind. Now try to prove that it is a 1/2-approximation. Are you able to prove it? What efforts have you made? What progress have you made so far and where specifically did you get stuck?
– D.W.
Sep 16 '17 at 14:06
• Asked a few times before... Sep 16 '17 at 14:27
• @YuvalFilmus could you please point me to one of those questions? Sep 16 '17 at 14:34
• Some of them appear in the "related" pane. All of them would mention "vertex cover", "independent set", and "approximation". Sep 16 '17 at 14:36

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$$.