In this, indirect, approach to the Hamiltonian cycle problem, we attempt to identify non-Hamiltonian graphs by infeasibility of suitably constructed systems of linear constraints. This approach is motivated by the fact that, in the space of discounted occupational measures of a Markov decision process induced by a graph, the convex hull of extreme points corresponding to Hamiltonian cycles is a well-defined polytope Q. The latter is empty if and only if the graph is non-Hamiltonian. While a complete characterisation of Q is a difficult problem, it is possible to construct a sequence of polytopes P1 ⊇ ... ⊇ Pk-1 ⊇ Pk ⊇ Q where each member of the sequence is determined by an increasing number of polynomially many linear constraints. The aim is to arrive at Pk that is sufficiently close to Q so that Pk is empty in all, or almost all, instances when Q is empty. In that sense, the condition Pk = ∅ constitutes a certificate of non-Hamiltonicity of the underlying graph. Of course, checking feasibility of Pk is a problem of polynomial complexity.
In Haythorpe  and Eshragh , preliminary investigations of this approach were conducted, and yielded encouraging experimental results. Subsequently, in Filar et al  it is shown that the approach correctly predicts the Hamiltonicity of cubic graphs of order 18 or less in all but 2 instances out of 45,982 such graphs.
 Eshragh, A. "Hamiltonian cycles and the space of discounted occupational measures." University of South Australia, 2011. Trove
 J.A. Filar, M. Haythorpe and S. Rossomakhine. "A reliable polynomial-complexity heuristic for detecting non-Hamiltonicity in cubic graphs." In preperation.
 Haythorpe, M. "Markov Chain based algorithms for the Hamiltonian cycle problem." University of South Australia, 2010. Systems Optimization Laboratory