Random walk approach

Exploiting a result due to Feinberg [6], we can constrain the set of discounted occupational measures (in a Mfarkov decision process induced by a given graph) by a single cut, and make a simple normalization to construct a polytope Hβ that is nonempty whenever the graph is Hamiltonian and which - in a prescribed sense - contains all the Hamiltonian cycles among its extreme points. While the latter polytope has been exploited as a base for two successful heuristic algorithms (e.g. see [1], [5]), we have evidence that it may also reveal certain fundamental properties of Hamiltonian graphs, when the parameter β is sufficiently near 1.

In particular, we can construct two smaller polytopes WHβ and WHpβ such that WHpβWHβHβ and, more importantly, the only extreme points that WHpβ and Hβ have in common correspond precisely to Hamiltonian cycles. This is, schematically, portrayed in the figure below. Recently, Filar and Eshragh [4] designed a random walk, pivoting, algorithm on the extreme points of WHpβ and Hβ that in - numerical testing - found Hamiltonian cycles in 2 to 34 random pivots for randomly generated (sparse) graphs with number of vertices ranging from 20 to 150.



As expected, the above random walk algorithm will find a Hamiltonian cycle (if there is one) in finite time, with probability one (see [4]). However, what makes this idea exciting is that the observed slow growth of the number of random pivots in N (number of vertices) suggests that the following, much more powerful, result may also be true.

Conjecture: Let A be a suitably designed random walk algorithm and Y be the random variable denoting the number of extreme points that A will need to examine to identify a Hamiltonian cycle (if there is one). Then there exist polynomials q1(log(β), N) and q2(log(β), N) (with positive coefficients of the leading power of N) such that for β sufficiently near 1, the probability Pr(Y > q1(log(β), N)) ≤ exp{-q2(log(β), N)}.

These results were first derived in Eshragh's PhD thesis [2] which was later published as [3].


[1] Ejov, V., Filar, J.A., Haythorpe, M. and Nguyen, G.T. "Refined MDP-based branch-and-fix algorithm for the Hamiltonian Cycle Problem." Mathematics of Operations Research, 34(3):758-768, 2009. ACM Digital Library

[2] Eshragh, A. "Hamiltonian cycles and the space of discounted occupational measures." University of South Australia, 2011. Trove 

[3] Eshragh, A. "Hamiltonian Cycles and the Space of Discounted Occupational Measure." Lambert Academic Publishers, Saarbrücken, 2011.

[4] Eshragh, A. and Filar, J.A. "Hamiltonian Cycles, Random Walks, and Discounted Occupational Measures." Mathematics of Operations Research, 36(2):258-270, 2011. Informs Online 

[5] Eshragh, A., Filar, J.A. and Haythorpe, M. "A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem." Annals of Operations Research, 189(1):103-125, 2011. SpringerLink

[6] Feinberg, E. "Constrained discounted Markov decision processes and Hamiltonian cycles." Mathematics of Operations Research, 25(1):130-140, 2000. JSTOR