Complexity of the Hamilton Cycle Problem

Introduction

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.

Algorithms

Cheeseman et al.'s backtracking algorithm

The two heuristics employed by the Cetal algorithm are:

  1. Start at the node with the highest connectivity
  2. 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:

  1. Start at the node with the lowest connectivity
  2. 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.

Legend

Represents a graph that has been determined to be hamiltonian.
Represents a graph that has been determined to be non-hamiltonian.
Represents a graph that took too long to analyze.

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.

Highlighted graph

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.