# 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... – Yuval Filmus Sep 16 '17 at 14:27
• @YuvalFilmus could you please point me to one of those questions? – Anna Vopureta 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". – Yuval Filmus Sep 16 '17 at 14:36


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