turing machines - approximation algorithm for hamiltonian cycle

Question

Assume g(G,v) is an approximation function (algorithm) that returns the size (number of edges) of the longest simple cycle that v belongs to in a directed graph G, with a mistake range of +5 -5.

Meaning:

Size of the longest simple cycle in G that v belongs to - 5 <= g(G,v) <= Size of the longest simple cycle in G that v belongs to +5

Prove that if g runs in polynomial time N=NP.

I tried to use the obvious - find an Hamiltonian path (or cycle) from a to b in Graph G by deleting all edges from all the vertices to a, and adding an edge from b to a, then if there is an Hamiltonian path, g(G,a) must return Size >= V-5, lets say it returns V, but if there isn't an Hamiltonian path, g(G,a) could also return V. I tried to use different variations of the graph, but still same result.

Is there a different approach I could use, maybe a different NP-complete problem ?

question from:https://stackoverflow.com/questions/65920793/approximation-algorithm-for-hamiltonian-cycle

Answer 1

Waitting for answers