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.