Best bounds for the longest path optimization problem in cubic Hamiltonian graph?
Check out
"Finding long paths and cycles in sparse Hamiltonian graphs"
by Feder, Motwani, and Subi from STOC 2000. AFAIK, this is the best algorithm known to date.