patternMinor
Approximation Algorithm for Independet Set Problem: Any Explanation Please?
Viewed 0 times
independetproblemapproximationpleaseanyalgorithmforsetexplanation
Problem
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.
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.
Solution
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})$.
What Corollary 3 does imply is that the graphs that Håstad uses have maximal degree $\Omega(n^{1-\epsilon})$.
Context
StackExchange Computer Science Q#53206, answer score: 4
Revisions (0)
No revisions yet.