A model of the coNP-complete non-Hamilton tour decision problem for directed graphs
A truncated permutation matrix polytope is defined as the convex hull of a proper subset of n-permutations represented as 0/1 matrices. We present a linear system that models the coNP-complete non-Hamilton tour decision problem based upon constructing the convex hull of a set of truncated permutation matrix polytopes. Define polytope Pn-1 as the convex hull of all n-1 by n-1 permutation matrices. Each extreme point of Pn-1 is placed in correspondence (a bijection) with each Hamilton tour of a complete directed graph on n vertices. Given any n vertex graph G(n), a polynomial sized linear system F-(n) is constructed for which the image of its solution set, under an orthogonal projection, is the convex hull of the complete set of extrema of a subset of truncated permutation matrix polytopes, where each extreme point is in correspondence with each Hamilton tour not in G(n). The non-Hamilton tour decision problem is modeled by F-(n) such that G(n) is non-Hamiltonian if and only if, under an orthogonal projection, the image of the solution set of F-(n) is Pn-1. The decision problem 'Is the projection of the solution set of F-(n)=Pn-1?' is therefore coNP-complete, and this particular model of the non-Hamilton tour problem appears to be new.
hamiltonicity projection extended formulation assignment polytope conp