Expected Computation Time for Hamiltonian Path problem
Yuri G. Gurevich, Saharon Shelah · SIAM Journal on Computing · 1987
One way to cope with an NP-hard problem is to find an algorithm that is fact on average with respect to a natural probability distribution on inputs. We consider from that point of view the Hamiltonian Path Problem. Our algorithm for the Hamiltonian Path Problem constructs or establishes the nonexistence of a Hamiltonian path. For a fixed probability p, the expected run-time of our algorithm on a random graph with n vertices and the edge probability p is $O(n)$. The algorithm is adaptable to directed graphs.