HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Approximation Algorithm for Independet Set Problem: Any Explanation Please?

Submitted by: @import:stackexchange-cs··
0
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.

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

Context

StackExchange Computer Science Q#53206, answer score: 4

Revisions (0)

No revisions yet.