Investigating for Hamiltonian Cycles through Random Walks
by
Ali Eshragh
University of South Australia
Coauthors: Jerzy Filar

We present a continuation of a line of research that embeds a graph in a Markov decision process (MDP). This embedding enables us to search for specific graph theoretic structures, such as Hamiltonian cycles, in the space of occupational measures usually associated with MDP’s that is well known to possess a polyhedral representation. In 2000, Feinberg showed that a certain polyhedral subset in that space contains all Hamiltonian cycles of a graph among its extreme points. We demonstrate that a further refinement of the latter possesses a number of additional desirable properties. In particular, for values of a parameter β called “the discount factor” that are close to 1 the refined polytope preserves all extreme points corresponding to Hamiltonian cycles while cutting off many other extreme points. This property offers an opportunity for developing new algorithms for finding Hamiltonian cycles. One presented here, is an algorithm that searches for Hamiltonian cycles by performing a random walk on extreme points of the refined polytope. We develop some theoretical properties of this random walk and present numerical results.

Date received: November 18, 2009