文章基本信息

标题：Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
本地全文：下载
作者：Per Austrin ; Subhash Khot ; Muli Safra 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2011
卷号：7
页码：27-43
DOI：10.4086/toc.2011.v007a003
语种：English
出版社：University of Chicago
摘要：We study the inapproximability of Vertex Cover and Independent Seton degree-$d$ graphs. We prove that: Vertex Cover is Unique Games-hard to approximate within a factor $2 - (2+o_d(1)) \frac{ \log\log d}{ \log d}$. This exactly matches the algorithmic result of Halperin (SICOMP 2002) up to the $o_d(1)$ term. Independent Set is Unique Games-hard to approximate within a factor $O (d/\log^2 d)$.This improves the $d/\log^{O(1)}(d)$ Unique Games hardness result of Samorodnitsky and Trevisan (STOC'06). Additionally, our proof does not rely on the construction of a query-efficient PCP.
关键词：vertex cover; independent set; bounded degree; hardness; approximation; Unique Games Conjecture