Connection between vertex cover and P=NP
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.