The Hamiltonian path problem has been proven to be NP-complete for both directed and undirected graphs through a reduction from vertex cover.

Sign up

Need help? accounthelp@everything2.com