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 .

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:

• Do you have to visit all the vertices or all the edges? - First verify that you really have a Hamiltonian cycle problem. As discussed in Section , fast algorithms exist for edge-tour, or Eulerian cycle, problems,   where you must visit all the edges without repetition. With a little cleverness, it is sometimes possible to reformulate a Hamiltonian cycle problem in terms of Eulerian cycles.   Perhaps the most famous such instance is the problem of constructing de Bruijn sequences, discussed in Section .
• Is there a serious penalty for visiting vertices more than once? - By phrasing the problem as minimizing the total number of vertices visited on a complete tour, we have an optimization problem that now allows room for heuristics and approximation algorithms.   For example, finding a spanning tree of the graph and doing a depth-first search, as discussed in Section , yields a tour with at most 2n vertices.     Using randomization or simulated annealing might bring the size of this down considerably.  
• Am I seeking the longest path in a directed acyclic graph (DAG)? - The problem of finding the longest path in a DAG can be solved in linear time using dynamic programming. This is about the only interesting case of longest path for which efficient algorithms exist.   
• Is my graph dense? - For sufficiently dense graphs, there always exists at least one Hamiltonian cycle, and further, such a cycle can be found quickly.   An efficient algorithm for finding a Hamiltonian cycle in a graph where all vertices have degree is given in [Man89].

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

XTango (see Section ) 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 .

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 .

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