A 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 very slow.

Answer 1

You just asked a million dollars . Finding Hamilton's path is an NP-complete problem. Some NP-hard problems can be solved in polynomial time using dynamic programming, but as far as I know, this is not one of them.

Answer 2

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

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

For example, the following is true: if each vertex of the graph has a degree of at least n / 2, then the graph has a Hamiltonian path. In fact, you can find it in O (n ² ), or IIRC even O (n log n) if you do it more smartly.
[Rough sketch: firstly, just connect all the vertices in some “Hamiltonian” cycle, it doesn’t matter if the edges are actually in the graph. Now for each edge (v, w) of your cycle, which is actually not on the graph, we consider the rest of the cycle: v ... w. Since deg (v) + deg (w)> = n, in your list (in this order) there are consecutive x, y such that w is a neighbor of x and v is a neighbor of y. [Evidence. Consider the {set of all neighbors w} and {the set of all successors in your list of neighbors v}; they should intersect.] Now change your cycle [v ... xy ... wv] to [vy ... wx ... v], instead it has at least one less invalid edge, so you need at most n iterations to get the true Hamiltonian cycle. Read more here .]

BTW: if what you are looking for is just a walk that includes all edges once, it is called Eulerian wandering and for graphs having it (the number of vertices of an odd degree is 0 or 2), you can quite easily find it in polynomial time (fast).

Answer 3

He is NP completed. But if you can find a good method, let me know and I will show you how to get rich.

Answer 4

Finding the best algorithm for the shortest is unlikely, since this is NP difficult. But there are a few heuristics that you could try, and you might want to consult your lectures for them;).

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

Answer 5

My Query: show that the RHAM search problem for finding the Hamiltonian cycle in column G is independently reducible. The search problem R is self-reducible if it reduces to solving the solution problem

SR={ x : R(x) ≠ ∅ }

Answer 6

Depending on how the graphs you are working with are generated, you can get the expected polynomial time against a random instance by doing a greedy path extension and then randomly changing the edge when it is stuck.

This works well against randomly generated relatively rare graphs guaranteed by the Hamiltonian move.

Answer 7

Hmm ... it depends on your definitions. The Hamiltonian trajectory is, of course, NP-complete. However, a Hamiltonian movement that can visit edges and vertices more than once (yes, it is still called the Hamiltonian while you add the blind bit at the end) can be calculated in O (p ^ 2logp) or O (max (c ^ 2plogp, | E |)), as long as your schedule satisfies a certain condition, which Dirac first proposed, and Takamizawa proved. See Takamizawa (1980), "An Algorithm for Finding a Short Closed Spanning Walk in a Graph."

Floor