Approximation Algorithm for Vertex Cover -

if p not equal np can shown there no approximation algorithm comes within k of optimal vertex cover, k fixed constant?

if question understood in terms of additive error, such algorithm not exist. aiming @ contradiction, suppose a such algorithm; means there nonnegative integer k such graph g,

a(g) <= tau(g) + k 

holds, a(g) cardinality of vertex cover of g generated a , tau(g) denotes cardinality of minimum vertex cover. let k chosen minimal respect existence of mentioned algorithm. in particular, have k => 1, since otherwise vertex cover problem solved in polynomial time, impossible unless p=np holds.

let g arbitraty graph; create graph g' taking k+1 isomorphic copies of g; then

tau(g') = (k + 1) tau(g) 

holds. furthermore obtain following.

a(g') <= tau(g) + k        = (k + 1) tau(g) + k 

let g* isomorphic copy of g in g' smallest vertex cover generated a; let a(g*) denote size of vertex cover. aiming @ contradiction, assume that

a(g*) >= tau(g*) + k 

holds. 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. contradiction approximation quality of a. means that

a(g*) < tau(g*) + k 

holds. tau(g*) = tau(g) holds, means have used a generate vertex cover of g cardinality strictly smaller than

tau(g) + k 

which contradiction, since k chosen minimally , construction steps can carried out within polynomially bounded running time, resulting in runtime bound polynomially bounded well.