patternMinor
Is it true that independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP?
Viewed 0 times
unlessindependentepsilontruethatinapproximableset
Problem
I was reading a paper and I came to the following :
"Since independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP (see [19]) for any fixed $\epsilon> 0$, the ..." where [19] is the following article : D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In STOC, pages 681–690, 2006.
My question: is it true that independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP? Because I cannot find this result in the cited article. However, I can find the results about max clique and chromatic number. What I am missing?
"Since independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP (see [19]) for any fixed $\epsilon> 0$, the ..." where [19] is the following article : D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In STOC, pages 681–690, 2006.
My question: is it true that independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP? Because I cannot find this result in the cited article. However, I can find the results about max clique and chromatic number. What I am missing?
Solution
Yes, this is true.
To see this, notice that cliques and independent sets are complementary. That is, a set of vertices $S$ is independent precisely when $S$ forms a clique in the complement of the graph. Intuitively, this means that if you had an approximation algorithm for finding a maximum clique, you could use it to find a maximum independent set by executing it on the complement graph.
To see this, notice that cliques and independent sets are complementary. That is, a set of vertices $S$ is independent precisely when $S$ forms a clique in the complement of the graph. Intuitively, this means that if you had an approximation algorithm for finding a maximum clique, you could use it to find a maximum independent set by executing it on the complement graph.
Context
StackExchange Computer Science Q#57536, answer score: 5
Revisions (0)
No revisions yet.