en.wikipedia.org/wiki/Unique_games_conjecture
1 correction found
2 − ε
In the Min vertex cover row, the NP-hardness factor is not 2−ε. The unconditional NP-hardness cited in the literature is √2−o(1); 2−ε is the stronger hardness known under the Unique Games Conjecture.
Full reasoning
This table entry appears to have lost the square-root symbol in the NP hardness column.
For minimum vertex cover, a 2017 STOC paper by Khot, Minzer, and Safra states that it is NP-hard to approximate Vertex Cover within a factor (\sqrt{2}-o(1)). Tel Aviv University's publication page for that paper summarizes the consequence explicitly: it is "NP-hard to approximate the Vertex Cover problem within a factor √2-o(1)."
By contrast, the 2−ε threshold is the well-known UGC-based hardness from Khot and Regev, not the ordinary NP-hardness entry. Oded Regev's publication list describes that separate result as "Vertex Cover Might be Hard to Approximate to within 2-ε".
So the post's visible text incorrectly shows 2−ε in the NP-hardness column for Min vertex cover; that column should be √2−ε (or more precisely √2−o(1), depending on notation).
2 sources
- On Independent Sets, 2-to-2 Games, and Grassmann Graphs - Tel Aviv University
A reduction that is sound in this non-standard sense implies that it is NP-hard to distinguish whether an n-vertex graph has an independent set of size (1-1/√2)n-o(n) or whether every independent set has size o(n), and consequently, that it is NP-hard to approximate the Vertex Cover problem within a factor √2-o(1).
- Oded Regev
Vertex Cover Might be Hard to Approximate to within 2-ε ... Subhash Khot, Oded Regev ... Journal of Computer and System Sciences 74(3), pp. 335-349, 2008.