What is the dynamic programming algorithm for finding a Hamiltonian cycle in a graph?

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

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.