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.

Solution 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.

Solution 2

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)

Comments

[mrk]

By increasing order, you mean just go over the number 0, 1, 2, ... or go over sets of size 0 first, then 1, then 2, then 3, ...?

[sidgeon smythe]

@staame I mean any order such that if A is a subset of B, then A occurs before B. You can indeed do this by iterating over sets by size, but you can also, for instance, just iterate over them in order of their bitwise representation (ie, go over integers 0 to 2^n, and interpret each as a set).

[mrk]

Thanks, so it's induction on graph size. If I understood correctly, it must be true that for any two numbers x,y. x < y implies x is a subset of y assuming that they intersect.

[sidgeon smythe]

@staame: Not exactly. If X is a subset of Y, then when you represent X and Y in binary (in the standard way, as a bitmap) as x and y respectively, you have x < y: because y has all the bits of x set, plus a few more bits set, it is a larger number. But two sets can intersect with neither being a subset of the other, and always one of the corresponding bitmap numbers will be smaller than the other — but this does not mean anything. As examples, let's represent X={0,1,3,5,7} by x=10101011 and Y={0,1,2,3,5,7} by y=10101111 and Z={1,3,6,7} by z=11001010. Then x<y<z, but X (or Y) isn't subset of Z.