{"id":72,"date":"2020-01-16T15:52:32","date_gmt":"2020-01-16T05:22:32","guid":{"rendered":"http:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/?page_id=72"},"modified":"2020-01-16T15:54:35","modified_gmt":"2020-01-16T05:24:35","slug":"linear-feasibility-models","status":"publish","type":"page","link":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/linear-feasibility-models\/","title":{"rendered":"Linear feasibility models"},"content":{"rendered":"

[vc_row][vc_column][vc_empty_space][vc_column_text]<\/p>\n

Linear feasibility models<\/h1>\n

In this, indirect, approach to the Hamiltonian cycle problem, we attempt to\u00a0identify 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<\/i><\/b>. The latter is empty if and only if the graph is non-Hamiltonian.\u00a0While a complete characterisation of Q<\/i> <\/b>is a difficult problem, it is possible to construct a sequence of polytopes\u00a0P<\/i><\/b>1<\/span><\/sub> \u2287 … \u2287\u00a0P<\/i><\/b>k-1<\/sub>\u00a0\u2287 P<\/i><\/b>k<\/span><\/sub> \u2287 Q<\/i> <\/b>where each member of the sequence is determined by an increasing number of polynomially many linear constraints. The aim is to arrive at P<\/i><\/b>k<\/span><\/sub> that is sufficiently close to Q<\/i><\/b> so that P<\/i><\/b>k<\/span><\/sub> is empty in all, or almost all, instances when Q<\/i><\/b> is empty. In that sense, the condition P<\/i><\/b>k<\/span><\/sub> = \u2205<\/b> constitutes a certificate of non-Hamiltonicity of the underlying graph. Of course, checking feasibility of P<\/i><\/b>k<\/span><\/sub> is a problem of polynomial complexity.<\/p>\n

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\u00a0the Hamiltonicity of cubic graphs of order 18 or less in all but 2 instances out of 45,982 such graphs.<\/p>\n

PUBLICATIONS<\/h3>\n

[1] Eshragh, A. “Hamiltonian cycles and the space of discounted occupational measures.” University of South Australia, 2011. Trove<\/a><\/p>\n

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

[3] Haythorpe, M. “Markov Chain based algorithms for the Hamiltonian cycle problem.” University of South Australia, 2010. Systems Optimization Laboratory<\/a>[\/vc_column_text][vc_empty_space][\/vc_column][\/vc_row]<\/p>\n<\/div>","protected":false},"excerpt":{"rendered":"

[vc_row][vc_column][vc_empty_space][vc_column_text] Linear feasibility models In this, indirect, approach to the Hamiltonian cycle problem, we attempt to\u00a0identify 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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":63,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-72","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages\/72","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/comments?post=72"}],"version-history":[{"count":0,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages\/72\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages\/63"}],"wp:attachment":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/media?parent=72"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}