Input: cubic Hamiltonian graph
feasible solution: A simple path
measure to optimize: length of the simple path
Design a polynomial-time algorithm that outputs the longest path it can find.
To my knowledge, longest path problem does not have polynomial-time constant-factor approximation in cubic Hamiltonian graphs unless P=NP. This problem is interesting since the input is cubic graph and has a n-length Hamiltonian cycle.
On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs, Journal of Algorithms 31, 249-268, 1999.