Polynomial time algorithm for finding a Hamiltonian walk in a graph

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

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

http://198.170.104.138/itj/2006/851-859.pdf :P

Answer 7

Hmmm. Had a look to the above paper posted by wlark, but it does not prove how efficient it is. The algorithm is not even formally proved. It could be O(anything !)

Answer 8

Is there any O(n^5) algorithm available ? I think I have a algo which can run in O(n^5).

Answer 9

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) ≠ ∅ }