The Hamiltonian path problem is: Given a
graph, is there a
simple open path that contains all the
vertices?
The Hamiltonian path problem has been proven to be NP-complete for both directed and undirected graphs through a reduction from vertex cover.