Complexity of the Hamilton Cycle Problem
Introduction
The figure on this page illustrates the complexity of the hamilton cycle problem, the problem of determining whether a path exists that visits every vertex in a graph exactly once and ends at the starting vertex. The inspiration for this page came from a paper by Cheeseman, Kanefsky and Taylor "Where the Really hard problems are" (1991), and a desire to enlarge and clarify their figures on this topic.
Algorithms
Depth-First
A simple depth-first search, with a random start and random ordering of neighbours
Cheeseman et al.'s backtracking algorithm
The two heuristics employed by the Cetal algorithm are:
- Start at the node with the highest connectivity
- Order the neighbouring nodes of the last visited node by their connections to unvisited nodes (more is better)
Horn's backtracking algorithm
The two heuristics employed by this backtrack algorithm are:
- Start at the node with the lowest connectivity
- Order the neighbouring nodes of the last visited node by their connections to unvisited nodes (less is better)
Vandergriend & Culberson's pruning algorithm
Vacul precedes search with a check for connectedness and cut-vertices (vertices that when removed cause the graph to be disconnected) to determine quickly if it is possible for the graph to be hamiltonian.
During search it removes edges in the graph that cannot possibly be in the hamilton cycle, reducing the search space and iterations needed to reach a conclusion.
Martello
Description will follow later.
Rubin
Description will follow later.