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.

Answers


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.


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! → N22N 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(n2), 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).


It's NP complete. But if you do manage to find a good method, let me know and I'll show you how to get rich.


Finding a better algorithm for the shortest is unlikely, as it is NP hard. But there are some heuristics that you could try, and perhaps you might want to consult your lecture notes for those ;) .

For less complexity you could find a short(ish) walk using the greedy algorithm.


My Query: Show that a search problem RHAM for finding a Hamiltonian cycle in the graph G is self-reducible A search problem R is self-reducible if it is Cook-reducible to a decision problem SR={ x : R(x) ≠ ∅ }


Depending on just how the graphs you're working with are generated you might be able to get expected polynomial time against a random instance by doing greedy path extension and then a random edge swap when that gets stuck.

This works well against randomly generated relatively sparse graphs guaranteed to have a Hamiltonian walk.


Hmmm.. this depends on what your definitions are. An hamiltonian path is certainly NP-complete. However, an hamiltonian walk which can visit edges and vertices more than once (yes it's still called hamiltonian so long as you add the walk bit at the end) can be calculated in O(p^2logp) or O(max(c^2plogp, |E|)) so long as your graph meets a certain condition which Dirac first conjectured and the Takamizawa proved. See Takamizawa (1980) "An algorithm for finding a short closed spanning walk in a graph".

Paul


Need Your Help

Vim case-insensitive filename completion

vim autocomplete case-sensitive tab-completion

I recently noticed how to configure bash to do case-insensitive filename completion (in /etc/inputrc, add: set completion-ignore-case on), now how do I get this in vim?