Linking subgraph isomorphism and the Hamilton tour decision problem using a linearized form of PGPT

Abstract

This paper presents convex polytope Q_0/1, the convex hull of all n! O(n²) permutation matrices specially extended into O(n ⁴) space. Q_0/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 O_0/1 corresponds to a permutation of the vertex labeling of an n vertex graph G_n, and a linear objective function is constructed whose optimal value is n (over Q _0/1) if an only if G_n is Hamiltonian. While a 'good' external representation of Q_0/1 is unlikely to exist, a polynomial sized relaxed formulation of Q_0/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 Q_0/1.