TY - GEN
T1 - Inapproximability of vertex cover and independent set in bounded degree graphs
AU - Austrin, Per
AU - Khot, Subhash
AU - Safra, Muli
N1 - Funding Information:
We thank an anonymous referee for helpful suggestions that helped improve the Letter. We appreciate useful discussions with Gregory Sivakoff, Jeffrey Crane, and Allyson Polak. We gratefully acknowledge support by NSF grant AST 03-07851, NASA/JPL contract 1228235, the Virginia Space Grant Consortium, and Frank Levinson through the Celerity Foundation. D. L. N. is also supported by the ARCS Foundation and the Green Bank Telescope Student Support Program. P. M. F. is supported by NASA GSRP and UVa dissertation fellowships.
PY - 2009
Y1 - 2009
N2 - We study the inapproximability of Vertex Cover and Independent Set on degree d graphs. We prove that: • Vertex Cover is Unique Games-hard to approximate to within a factor 2-(2+od(1))/log log d/log d . This exactly matches the algorithmic result of Halperin [1] up to the o d(1) term. • Independent Set is Unique Games-hard to approximate to within a factor O/( d/log2 d ). This improves the d/log O(1)(d) Unique Games hardness result of Samorodnitsky and Trevisan [2]. Additionally, our result does not rely on the construction of a query efficient PCP as in [2].
AB - We study the inapproximability of Vertex Cover and Independent Set on degree d graphs. We prove that: • Vertex Cover is Unique Games-hard to approximate to within a factor 2-(2+od(1))/log log d/log d . This exactly matches the algorithmic result of Halperin [1] up to the o d(1) term. • Independent Set is Unique Games-hard to approximate to within a factor O/( d/log2 d ). This improves the d/log O(1)(d) Unique Games hardness result of Samorodnitsky and Trevisan [2]. Additionally, our result does not rely on the construction of a query efficient PCP as in [2].
UR - http://www.scopus.com/inward/record.url?scp=70350626961&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350626961&partnerID=8YFLogxK
U2 - 10.1109/CCC.2009.38
DO - 10.1109/CCC.2009.38
M3 - Conference contribution
AN - SCOPUS:70350626961
SN - 9780769537177
T3 - Proceedings of the Annual IEEE Conference on Computational Complexity
SP - 74
EP - 80
BT - Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009
T2 - 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009
Y2 - 15 July 2009 through 18 July 2009
ER -