How to prove NP-hardness of a Hamiltonian Path problem by reducing longest-path problem? I know how to prove longest-path problem by reducing Hamiltonian Path problem.
Here I want to prove NP-hardness of a Hamiltonion Path problem by reducing longest-path problem. (pretend we know longest-path problem is NP-hardness, not Hamiltonion Path problem)
I'm wondering if it is possible to reduce Hamiltonian Path problem to longest path problem.
Is there any way I can do that?
Suppose you have a graph $G$ of order $n$. $G$ has a simple path of length $\geq n - 1$ if and only if $G$ has a hamiltonian path.