Connection between vertex cover and P=NP

Question

I read about vertex cover and i can't understand why the following occurs. Tried to look and research on the site and in other places but still can't understand it.

In an undirected graph $G(V,E)$, vertex cover is a set of edges U so that every Edge in E has at least one end at U.

Defining the following function: $f(G,v)$ equals to the minimal vertex cover that v belongs to.

Why if it is possible to calculate in a polynomial time the function $g(G,v)$ and it is guaranteed that $f(G,v) -5 \leq g(G,v) \leq f(G,v) +5$ then P=NP?

(Meaning if we can estimate f in a constant boundary of +5 in a polynomial time, then P=NP?)

What i think:since vertex cover is an NP-COMPLETE language, and so is the minimal vertex cover, if it is bounded by +-5, a linear bound. then if known that $g(G,v)$ can be calculated in polynomial time and we can also show that it's boundaries are $f(G,v) - 5$ and $f(G,v)+5$, then P = NP.

So regarding minimal vertex cover, the problem is $min(f(x)| x \in vertexcover(G))$. so an algorithm for minvertexcover is: initialize {cover<-0, Edges<-0}; until there are no more edges $e \in E$ in G: 1)add u,v to cover; 2)add $e_i$ to Edges; 3)remove u,v from G and adjacent edges.

Now, since $|Edges = 2 * cover|$, then for a possible solution, meaning vertex cover that covers all the edges, that possible solution will be more than Edges, so that possible solution will be bigger than 2 * Edges.

Since that possible solution $\geq 2 * Edges$, it means that the possible solution is $\geq f(G,v) + 5$, so it is bounded. now if we can calculate $g(G,v)$ in a polynomial time, it means we can calculate the possible solution in at least 2 * polynomial time, which is still polynomial. so it means that if $g(G,v)$ can be calculated in polynomial time, and the given +-5 boundary exists, then P=NP.

How to prove it correctly and efficiently? spent long days on it and would appreciate seeing how to do it correctly

Answer 1

I will assume that $g(G, v)$ computes a valid vertex cover, so it can never report a more optimal solution, and does so in polynomial time. We know that vertex cover is NP-hard to approximate within a factor below 1.36: http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf. Since $g(G, v)$ reports a solution at most 5 more than optimal, we can scale the graph such that $(f(G,v) + 5) / f(G, v)) \leq 1.36$, which results in $f(G, v) \geq 14$.

Furthermore, vertex cover is fixed parameter tractable in the solution size. In other words, we can compute whether $G$ admits a vertex cover of a fixed size in polynomial time. Hence, we apply the fixed parameter tractable algorithm up to $k = 13$. If no solution has been found, use $g$. We now have a polynomial time algorithm that can solve any set cover instance within a factor below 1.36 times the optimal solution, which is a contradiction unless P = NP.

Corollary: it is impossible to have a computable algorithm that outputs a vertex cover of size at most $OPT + c$, where $c \geq 0$ is a constant, in polynomial time, unless P = NP.