## Abstract

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 sub graph of (1 - ε)N vertices, it is NP-hard to find an independent set of N/q^{k+1} vertices. This substantially improves upon the work of Dinur et al. [DKPS] who gave a corresponding bound of N/q^{2}. Our result implies that for any positive integer k, given a graph that has an independent set of ≈ (2^{k} + 1)^{-1} fraction of vertices, it is NP-hard to find an independent set of (2^{k} + 1)^{-(k+1)} fraction of vertices. This improves on the previous work of Engebretsen and Holmerin [EH] who proved a gap of ≈ 2^{-k} vs 2^{-(k 2)}, which is best possible using techniques (including those of [EH]) based on the query efficient PCP of Samorodnitsky and Trevisan [3].

Original language | English (US) |
---|---|

Title of host publication | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |

Pages | 380-389 |

Number of pages | 10 |

DOIs | |

State | Published - 2012 |

Event | 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 - New Brunswick, NJ, United States Duration: Oct 20 2012 → Oct 23 2012 |

### Other

Other | 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 |
---|---|

Country | United States |

City | New Brunswick, NJ |

Period | 10/20/12 → 10/23/12 |

## Keywords

- Coloring
- Graphs
- Hardness
- Independent-Set
- PCP

## ASJC Scopus subject areas

- Computer Science(all)