What is the dynamic programming algorithm for find

Question

What is dynamic programming algorithm for finding a Hamiltonian cycle in an undirected graph? I have seen somewhere that there exists an algorithm with O(n.2^n) time complexity.

Answer 1

I can't pluck out that particular algorithm, but there is more about Hamiltonian Cycles on The Hamiltonian Page than you will likely ever need. :)

This page intends to be a comprehensive listing of papers, source code, preprints, technical reports, etc, available on the Internet about the Hamiltonian Cycle and Hamiltonian Path Problems as well as some associated problems.

(original URL, currently 404), (Internet Archive)

Answer 2

There is indeed an O(n2ⁿ) dynamic-programming algorithm for finding Hamiltonian cycles. The idea, which is a general one that can reduce many O(n!) backtracking approaches to O(n²2ⁿ) or O(n2ⁿ) (at the cost of using more memory), is to consider subproblems that are sets with specified "endpoints".

Here, since you want a cycle, you can start at any vertex. So fix one, call it x. The subproblems would be: “For a given set S and a vertex v in S, is there a path starting at x and going through all the vertices of S, ending at v?” Call this, say, poss[S][v].

As with most dynamic programming problems, once you define the subproblems the rest is obvious: Loop over all the 2ⁿ sets S of vertices in any "increasing" order, and for each v in each such S, you can compute poss[S][v] as:

poss[S][v] = (there exists some u in S such that poss[S−{v}][u] is True and an edge u->v exists)

Finally, there is a Hamiltonian cycle iff there is a vertex v such that an edge v->x exists and poss[S][v] is True, where S is the set of all vertices (other than x, depending on how you defined it).

If you want the actual Hamiltonian cycle instead of just deciding whether one exists or not, make poss[S][v] store the actual u that made it possible instead of just True or False; that way you can trace back a path at the end.