This page contains additional information to "A Predictive Data Analytic for the Hardness of Hamiltonian Cycle Problem Instances". All results can be downloaded in csv format here (zip).
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.
Two simple backtrack algorithms (with 2 specific heuristics, more on that later) for this problem were run on a large set of (randomly generated) graphs of increasing average connectivity. More specifically: for each average connectivity 20 graphs were generated for both 16- and 24-vertex graphs. The amount of iterations (divided by the graph size) needed by the algorithm to come to a conclusion is displayed here.
The two heuristics employed by the Cetal algorithm are:
The two heuristics employed by this backtrack algorithm are:
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.
Hovering over a data point shows a histogram of the connectivity in that graph, with the connectivity on the x-axis and the amount of vertices that have that connectivity on the y-axis.
Clicking on a data point highlights all data points with the same graph, allowing performance comparison between algorithms.
The currently highlighted graph is displayed below. If it contains a Hamilton cycle, the edges in the cycle are green. The color and label of a node indicate its degree (a.k.a. connectivity).
Dragging a node fixes it to a location, double clicking makes it free to move again.