Polynomial time algorithm for finding a Hamiltonian walk in a graph [closed]

Question

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

My algorithm is N factorial and is really slow.

Answer 1

In general, as the (decision version of the) Hamiltonian Path problem is NP-complete, you cannot hope to get a polynomial-time algorithm for finding Hamiltonian paths. You can slightly speed it up with the usual N! → N²2^N dynamic programming trick (compute hp[v][w][S] = "is there a path that has endpoints v and w and whose vertices are the subset S" for every subset S and every two vertices v and w in it using DP), but that's still exponential.

However, there are many special kinds of graphs for which Hamiltonian paths will always exist, and they can be found easily (see work of Posa, Dirac, Ore, etc.)

For instance, the following is true: If every vertex of the graph has degree at least n/2, then the graph has a Hamiltonian path. You can in fact find one in O(n²), or IIRC even O(n log n) if you do it more cleverly.
[Rough sketch: First, just connect all vertices in some "Hamiltonian" cycle, nevermind if the edges are actually in the graph. Now for every edge (v,w) of your cycle that is not actually in the graph, consider the rest of the cycle: v...w. As deg(v)+deg(w)>=n, there exist consecutive x,y in your list (in that order) such that w is a neighbour of x and v is a neighbour of y. [Proof: Consider {the set of all neighbours of w} and {the set of all successors in your list of neighbours of v}; they must intersect.] Now change your cycle [v...xy...wv] to [vy...wx...v] instead, it has at least one less invalid edge, so you'll need at most n iterations to get a true Hamiltonian cycle. More details here.]

BTW: if what you are looking for is just a walk that includes every edge once, it's called an Eulerian walk and for graphs that have it (number of vertices of odd degree is 0 or 2), one can quite easily be found in polynomial time (fast).