Hardness of Finding Independent Sets in Almost q-Colorable Graphs
Subhash Khot, Rishi Saket · 2012
We show that for any ε >; 0, and positive integers k and q such that q ≥ 2k+ 1, given a graph on N vertices that has a q-colorable induced subgraph of (1 - ε)N vertices, it is NP-hard to find an independent set of N/qk+1vertices. This substantially improves upon the work of Dinur et al. [1] who gave a corresponding bound of N/q2. Our result implies that for any positive integer k, given a graph that has an independent set of ≈ (2k+ 1)-1fraction of vertices, it is NP-hard to find an independent set of (2k+ 1)-(k+1)fraction of vertices. This improves on the previous work of Engebretsen and Holmerin [2] who proved a gap of ≈ 2-kvs 2-(k:2), which is best possible using techniques (including those of [2]) based on the query efficient PCP of Samorodnitsky and Trevisan [3].