Search code examples
algorithmnp-complete

Polynomial time algorithm for finding a Hamiltonian walk in a graph

Is there a polynomial time algorithm for finding a Hamiltonian walk in a graph?

My algorithm is N factorial and is really slow.

Solution

  • You just asked the million dollar question. Finding a Hamilton path is an NP-complete problem. Some NP-hard problems can be solved in polynomial time using dynamic programming, but (to my knowledge) this is not one of them.