# Linear feasibility models

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

**is a difficult problem, it is possible to construct a sequence of polytopes**

*Q*

*P*_{1}⊇ … ⊇

*P*_{k-1}⊇

*P*_{k}⊇

**where each member of the sequence is determined by an increasing number of polynomially many linear constraints. The aim is to arrive at**

*Q*

*P*_{k}that is sufficiently close to

**so that**

*Q*

*P*_{k}is empty in all, or almost all, instances when

**is empty. In that sense, the condition**

*Q*

*P*_{k}=

**∅**constitutes a certificate of non-Hamiltonicity of the underlying graph. Of course, checking feasibility of

*P*_{k}is a problem of polynomial complexity.

In Haythorpe [3] and Eshragh [1], preliminary investigations of this approach were conducted, and yielded encouraging experimental results. Subsequently, in Filar et al [2] 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.

### PUBLICATIONS

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

[2] J.A. Filar, M. Haythorpe and S. Rossomakhine. “A reliable polynomial-complexity heuristic for detecting non-Hamiltonicity in cubic graphs.” In preperation.

[3] Haythorpe, M. “Markov Chain based algorithms for the Hamiltonian cycle problem.” University of South Australia, 2010. Systems Optimization Laboratory