Theory of Computing
-------------------
Title     : Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
Authors   : Per Austrin, Subhash Khot, and Muli Safra
Volume    : 7
Number    : 3
Pages     : 27-43
URL       : https://theoryofcomputing.org/articles/v007a003

Abstract
--------

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 within a factor
       2 - (2+o_d(1)) \log\log d / \log d.
 
     This exactly matches the algorithmic result of  Halperin (SICOMP'02) 
     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 result does 
     not rely on the  construction of a query efficient PCP.