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.