I am reading this note on approximation algorithms for independet set problem. I am confused of Theorem 1. and Corollary 3.

Here is the statement of Theorem 1.

Theorem 1 (Hastad [1]) Unless P = NP there is no $\frac{1}{n^{1-\epsilon}}$-approximation for MIS for any fixed $\epsilon>0$ where $n$ is the number of nodes in the given graph.

Here is the statement of Corollary 3.

Corollary 3 Greedy gives a $\frac{1}{\Delta+1}$-approximation for (unweighted) MIS in graphs of degree at most $\Delta$.

I feel like there is a contradiction between Theorem 1. and Corollary 3., no? Or because the graph in Corollary 3. is a special one with degree at most $\Delta$?

[1] J. Hastad. "Clique is Hard to Approximate within $n^{1-\epsilon}$"􀀀. Acta Mathematica, 182:105{142, 1999.


In general, the maximal degree in a graph can be as large as $n-1$. Therefore on general graphs, the greedy algorithm is only guaranteed to give a $1/n$ approximation, which you can also obtain by returning an arbitrary vertex.

What Corollary 3 does imply is that the graphs that Håstad uses have maximal degree $\Omega(n^{1-\epsilon})$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.