Snakes and Ladders Heuristic


The Snakes and Ladders Heuristic (SLH) is a polynomial-complexity algorithm inspired by the famous Lin-Kernighan (L-K) heuristic for solving the Travelling Salesman Problem. Although it is not guaranteed to find a Hamiltonian cycle in a Hamiltonian graph, preliminary empirical experiments on many graphs (not exceeding 5000 vertices) have succeeded in all cases. Though it is well known that L-K-type algorithms can be used to solve instances of HCP (by casting them as a TSP), SLH differs from these approaches in several fundamental ways. First, the requirement of improvement at each iteration, which is central to L-K, is removed. Second, we use some transformations not generally used in L-K (as they violate conditions of L-K, but not of SLH) that improve the efficiency of the heuristic. Third, a stopping rule is invoked if a maximum number (set to N3 in our implementation) of iterations have been performed without any improvement. Finally, SLH runs on any prescribed starting orientation, as opposed to L-K that relies heavily on repeated randomisations. These differences are elaborated on below.

The name Snakes and Ladders Heuristic comes from our representation of the heuristic. Let C be a circle, and G be a simple undirected graph containing N vertices. Then the vertices of G can be placed on C in some order, and all edges of G between adjacent vertices on C can be represented as arcs on C. A path of k connected edges of G that form a continuous arc on C is called a "k-snake", and an isolated vertex on C is considered to be a 0-snake. The arrangement on C of all the k-snakes is called a "slither".

The edges that are not a part of the slither are represented as chords of the circle, which we call "ladders". If the total number of edges forming all the k-snakes in a slither is less than N, then we say that the slither contains at least one "gap". A Hamiltonian cycle then is simply a slither consisting of a single N-snake, or equivalently, a slither with 0 gaps. The aim of SLH is to construct a slither with 0 gaps by monotonically reducing the number of gaps, if possible, and opening additional gaps if improvement is otherwise impossible. If N3 iterations have passed without a reduction in the number of gaps, SLH terminates and reports that the graph is likely to be non-Hamiltonian.

SLH has been implemented in C++. It has been tested on all 664 graphs listed on Gordon Royle's Extended Foster's Census list, and successfully solved all graphs in under 3 minutes total running time.

SLH succeeded in finding Hamiltonian cycles in the famously difficult Generalized Petersen Cubic Graphs, of up to 1000 vertices, that contain only three such cycles.

SLH has also been tested on all HCP instances from the University of Heidelberg's TSPLIB website, where examples range from 1000 - 5000 vertices, and has successfully solved all graphs. The largest of these was solved in under 1 minute. These time results were all obtained on a Dell Optiplex 990 laptop.

 

Interested readers are encouraged to try the SLHWeb Interface that allows users to submit their own graphs (in edge-list format) to SLH, and displays the solution process in real-time as an animation.