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