next up previous contents index CD CD Algorithms
Next: Graph Partition Up: Graph Problems: Hard Problems Previous: Traveling Salesman Problem

Hamiltonian Cycle



Input description: A graph G = (V,E).

Problem description: Find an ordering of the vertices such that each vertex is visited exactly once.

Discussion: The problem of finding a Hamiltonian cycle or path in a graph is a special case of the traveling salesman problem, one where each pair of vertices with an edge between them is considered to have distance 1, while nonedge vertex pairs are separated by distance tex2html_wrap_inline29453 .

Closely related is the problem of finding the longest path or cycle in a graph, which occasionally arises in pattern recognition problems.     Let the vertices in the graph correspond to possible symbols, and let edges link symbols that can possibly be next to each other.   The longest path through this graph is likely the correct interpretation.

The problems of finding longest cycles and paths are both NP-complete, even on very restrictive classes of unweighted graphs. There are several possible lines of attack, however:

If you really must know whether your graph is Hamiltonian, backtracking with pruning is your only possible solution.   Before you search, it pays to check whether your graph is biconnected (see Section gif).   If not, this means that the graph has an articulation vertex whose deletion will disconnect the graph and so cannot be Hamiltonian.

Implementations: The football program of the Stanford GraphBase (see Section gif) uses a stratified greedy algorithm to solve the asymmetric longest path problem. The goal is to derive a chain of football scores in order to establish the superiority of one football team over another. After all, if Virginia beat Illinois by 30 points, and Illinois beat Stony Brook by 14 points, then by transitivity Virginia would beat Stony Brook by 44 points if they played, right? We seek the longest path in a graph where the weight of an edge (x,y) is the number of points x beat y by.    

Nijenhuis and Wilf [NW78] provide an efficient routine to enumerate all Hamiltonian cycles of a graph by backtracking. See Section gif. Algorithm 595 [Mar83] of the Collected Algorithms of the ACM is a similar Fortran code that can be used as either an exact procedure or a heuristic by controlling the amount of backtracking.   See Section gif.  

XTango (see Section gif) is an algorithm animation system for UNIX and X-windows,   which includes an animation of a backtracking solution to the knight's tour problem.  

Combinatorica [Ski90] provides a Mathematica backtracking implementation of Hamiltonian cycle.     See Section gif.

Notes: Hamiltonian cycles - circuits that visit each vertex of a graph exactly once - apparently first arose in Euler's study of the knight's tour problem, although they were popularized by Hamilton's ``Around the World'' game in 1839.   Good expositions of the proof that Hamiltonian cycle is NP-complete [Kar72] include [Baa88, CLR90, GJ79].

Techniques for solving optimization problems in the laboratory using biological processes have recently attracted considerable attention.   In the original application of these ``biocomputing'' techniques, Adleman [Adl94b] solved a seven-vertex instance of the directed Hamiltonian path problem. Unfortunately, this approach requires an exponential number of molecules, and Avogadro's number implies that such experiments are inconceivable   for graphs beyond tex2html_wrap_inline29459 .

Related Problems: Eulerian cycle (see page gif), traveling salesman (see page gif).    

next up previous contents index CD CD Algorithms
Next: Graph Partition Up: Graph Problems: Hard Problems Previous: Traveling Salesman Problem

Mon Jun 2 23:33:50 EDT 1997