Hamiltonian(t)-an ant-inspired heuristic for recognizing Hamiltonian graphs

Abstract

Given a graph G(V,E), we consider the problem of deciding whether G is Hamiltonian, that is, whether or not there is a simple cycle in E spanning all vertices in V. This problem is known to be NP-complete, hence cannot be solved in time polynomial in |V| unless P=NP. The problem is a special case of the Travelling Salesperson Problem (TSP), that was extensively studied in the literature, and has recently been attacked by various ant-colony methods. We address the Hamiltonian cycle problem using a new ant-inspired approach, based on repeated covering of the graph. Our method is based on a process in which an ant traverses the graph by moving from vertex to vertex along the edges while leaving traces in the vertices, and deciding on the next step according to the level of traces in the surrounding neighborhood. We show that Hamiltonian cycles are limit cycles of the process, and investigate the average time needed by our ant process to recognize a Hamiltonian graph, on the basis of simulations made over large samples of random graphs with varying density of edges. © 1999 IEEE.