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:

  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.

Martello

Description will follow later.

Rubin

Description will follow later.

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.