# Connection between vertex cover and P=NP

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

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.