Linking subgraph isomorphism and the Hamilton tour decision problem using a linearized form of PGPT - Gismondi S.J., (Utilitas Mathematica, 2008)
This paper presents convex polytope Q0/1, the convex hull of all n! O(n2) permutation matrices specially extended into O(n 4) space. Q0/1 and a polynomial sized relaxed formulation were conceived by Ted Swart in 1991 [3], To help illustrate properties of Q 0/1, a model of the Hamilton tour decision problem is created as an instance of subgraph isomorphism - 'viewed from the perspective of Q 0/1'. Each extreme point of O0/1 corresponds to a permutation of the vertex labeling of an n vertex graph Gn, and a linear objective function is constructed whose optimal value is n (over Q 0/1) if an only if Gn is Hamiltonian. While a 'good' external representation of Q0/1 is unlikely to exist, a polynomial sized relaxed formulation of Q0/1 is presented, leading to an integer programming formulation of the Hamilton tour decision problem. Dim(aff(Q 0/1)) is computed, followed by discussion and presentation of a series of extended relaxed formulations of Q0/1.