If P is not equal to NP can it be shown that there is no approximation algorithm which comes within k of the optimal vertex cover, where k is a fixed constant?
If the question is to be understood in terms of an additive error, such an algorithm does not exist. Aiming at a contradiction, suppose A is such an algorithm; this means that there is a nonnegative integer k such that for any graph G,
A(G) <= tau(G) + k
holds, where A(G) is the cardinality of the vertex cover of G generated by A and tau(G) denotes the cardinality of a minimum vertex cover. Let k be chosen minimal with respect to the existence of the mentioned algorithm. In particular, we have k => 1, since otherwise the vertex cover problem could be solved in polynomial time, which is impossible unless P=NP holds.
Let G be an arbitraty graph; create a graph G' by taking k+1 isomorphic copies of G; then
tau(G') = (k + 1) tau(G)
holds. Furthermore we obtain the following.
A(G') <= tau(G) + k
= (k + 1) tau(G) + k
Let G* be the isomorphic copy of G in G' with the smallest vertex cover generated by A; let A(G*) denote the size of this vertex cover. Aiming at a contradiction, we assume that
A(G*) >= tau(G*) + k
holds. This means that
A(G') >= (k + 1) A(G*)
>= (k + 1) (tau(G*) + k)
= (k + 1) (tau(G) + k)
= (k + 1) tau(G) + k + k^2
> (k + 1) tau(G) + k
holds, since k > 0 holds. This is a contradiction to the approximation quality of A. This means that
A(G*) < tau(G*) + k
holds. As tau(G*) = tau(G) holds, this means that we have used A to generate a vertex cover of G with cardinality strictly smaller than
tau(G) + k
which is a contradiction, since k was chosen minimally and all construction steps can be carried out within a polynomially bounded running time, resulting in a runtime bound which is polynomially bounded as well.