Complexity reductions to Hamiltonian Path?
For undirected graphs, you can build a graph $G$ for every constant $0&lt;c&lt;1$ from an $n$-variate CNF SAT instance $I$ such that 


$G$ has $N=\operatorname{poly}(n)$ vertices
If $I$ is satisfiable, then $G$ has a Hamiltonian cycle
If $I$ is not satisfiable, then $G$ has no path of length $N-N^c$.


Karger Motwani Ramkumar 1997

For directed graphs, you can build a graph $G$ for every constant $0&lt;c&lt;1$ from an $n$-variate CNF SAT instance $I$ such that 


$G$ has $N=\operatorname{poly}(n)$ vertices
If $I$ is satisfiable, then $G$ has a Hamiltonian cycle
If $I$ is not satisfiable, then $G$ has no path of length $N^{1-c}$.


Björklund Husfeldt Khanna 2004