About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
FOCS 2012
Conference paper
Hardness of finding independent sets in almost q-colorable graphs
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/qk+1 vertices. This substantially improves upon the work of Dinur et al. [DKPS] 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)-1 fraction 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 [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]. © 2012 IEEE.