# 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

**WH**

*such that*

^{p}_{β}**WH**

*⊂*

^{p}_{β}**WH**

*⊂*

_{β}**H**

*and, more importantly, the only extreme points that*

_{β}**WH**

*and*

^{p}_{β}**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*

_{β}**WH**

*and*

^{p}_{β}**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.*

_{β}