Random walk approach
Exploiting a result due to Feinberg , 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 , ), 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  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.