FHCP Banner Image

Named after Sir William Hamilton’s investigations of the dodecahedral graph in 1857, the Hamiltonian cycle problem (HCP, for short) is a classical graph theory problem that can be summarised thus:

Given a graph containing N vertices determine whether it contains a simple cycle of length N.

Such a cycle is called a Hamiltonian cycle. The HCP has become a challenge that attracts mathematical minds both in its own right and because of its close relationship to the famous Travelling salesman problem (TSP), that calls for the identification of a Hamiltonian cycle with the lowest cost possible in a graph where every edge has a known cost associated with “travelling” along that edge. An efficient solution of the TSP would have an enormous impact in operations research, optimisation and computer science. However, from a mathematical perspective the underlying difficulty of the TSP is, perhaps, hidden in the Hamiltonian cycle problem. Hence, we focus on the latter.

The FHCP is a team project that aims to exploit novel stochastic and deterministic techniques to (i) explain the underlying theoretical difficulty of the HCP, (ii) characterise classes of  graphs that are particularly hard to solve and (iii) produce world-class algorithms that enable the efficient solution of most instance of the problem on graphs not exceeding 5000 vertices.

Based at Flinders University, South Australia, FHCP is led by Jerzy Filar and Vladimir Ejov. The team includes Flinders University students, research fellows and eminent national and international collaborators. FHCP team members have developed numerous approaches to analysing and solving the Hamiltonian cycle problem. A summary of these approaches is given below, with the most recent ideas listed first. For more detail, visit the respective project pages.

Visualisation of a solution to Euler’s Knight’s Tour Problem.


Snakes and Ladders Heuristic

A graph can be displayed by placing its vertices in some order on a circle. Then, any arcs between adjacent vertices on the circle are rendered as arcs (which we call snakes), while other arcs are rendered  as chords (which we call ladders). The snakes and ladders heuristic uses operations, inspired by the Lin–Kernighan heuristic, to reorder the vertices on the circle in order to transform some ladders into snakes. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time. Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that SLH is successful even in cases where such cycles are extremely rare, and the heuristic performs quickly even on very large graphs.

Determinant Interior Point Algorithm

A key result in 2008 by Ejov et all demonstrates that the Hamiltonian cycle problem may be recast as the maximisation of particular determinant with respect to only linear constraints. This formulation enables an interior point algorithm to take advantage of the considerable sparsity inherent in the more difficult instances of the Hamiltonian cycle problem. Through the use of a sparse LU decomposition, derivatives of the objective function are computed very efficiently.

Variance of first hitting times

In 1994, Filar and Krass described the process of embedding the Hamiltonian cycle problem in a Markov decision process. This embedding allows the natural amalgamation of standard graph theory techniques with those from Markov chain theory. Theoretical results enable the recasting of the Hamiltonian cycle problem as optimisation models with decision variables and objective functions previously unconsidered in graph theory.

Linear feasibility models

The Hamiltonian cycle problem can be recast precisely as a nonlinear feasibility problem. Linear relaxations exist but do not guarantee a meaningful solution, and indeed such solutions are uncommon even in small graphs. However, we are able to construct linear feasibility problems that are feasible for all Hamiltonian graphs, but infeasible for almost all non-Hamiltonian graphs.

Genetic theory of cubic graphs

We propose a partitioning of all cubic graphs into two disjoint categories, namely genes and descendants. Through the use of six breeding operations, every descendant can be obtained from a particular family of genes called that graph’s ancestor genes. The ancestor genes for a graph can be identified in polynomial time. A descendant inherits many graph theoretic properties from its ancestor genes.

Fractal-like structure of cubic graphs

For each cubic graph, the eigenvalues of its adjacency matrix can be considered. For each graph we obtain a 2-dimensional point, and we plot this point for all cubic graphs of a given size. A striking thread-like structure is produced which displays fractal properties. At each level, the separation of the threads corresponds to the presence of geodesics of given sizes.

Branch-and-fix approach

Branch and bound algorithms have been used to solve the Hamiltonian cycle problem since it was first posed, but perform very poorly even for moderate-sized graphs. We propose a non-standard branch-and-fix algorithm, designed for cubic graphs, that incorporates several checks and fathoming routines inspired by the MDP embedding to improve efficiency.

Random walk approach

Theoretical results obtained by the MDP embedding enable the construction of two polytopes whose common extreme points all correspond to Hamiltonian cycles. A random walk algorithm that attempts to minimise the Euclidian distance between pairs of extreme points from the two polytopes has displayed surprisingly strong results.

Cross-entropy/optimisation hybrid approach

The process of solving the Hamiltonian cycle problem using the cross-entropy method is well-known, but its eficiency dwindles for moderately large graphs. We use a hybrid algorithm that uses the probabilities gained from cross-entropy to power a linear programming heuristic which proven very fruitful for graphs previously unsolvable by the cross-entropy method.

Wedged-MIP heuristic

The Hamiltonian cycle problem is cast as a mixed integer program in which linear sums of decision variables are restricted to very thin wedge-like regions. An implementation in CPLEX succeeds in solving some large instances of the Hamiltonian cycle problem, including an irregular 2000-vertex graph.

We welcome any queries or suggestions. Please feel free to Contact Us!