Distinguising between the cases of low or high cover number Is there a known result saying that for some constants $0 &lt; a &lt; b &lt; 1$, it is NP-hard to distinguish a graph having vertex cover number at most $a \cdot n$ from a graph having vertex cover number at least $b \cdot n$? Here n is the number of vertices in the input graph. In other words, I want to know that (unless P = NP) there is no poly-time algorithm that accepts graphs with vertex-cover number at most $a \cdot n$, rejects graphs with vertex-cover number at least $b \cdot n$, and can return anything for a graph whose vertex-cover number is in between.
Proving hardness of this sort of gap problem is usually how hardness of approximation is proved. For vertex cover, Håstad's famous paper (Theorem 7.1.) showed what you are asking for with $a=3/4$ and $b=7/8$.