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 Q is a difficult problem, it is possible to construct a sequence of polytopes P₁ ⊇ … ⊇ P_k-1 ⊇ P_k ⊇ Q where each member of the sequence is determined by an increasing number of polynomially many linear constraints. The aim is to arrive at P_k that is sufficiently close to Q so that P_k is empty in all, or almost all, instances when Q is empty. In that sense, the condition 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