Authors: SJ Gismondi ER Swart
Publish Date: 2004/04/28
Volume: 100, Issue: 3, Pages: 471-483
Abstract
A truncated permutation matrix polytope is defined as the convex hull of a proper subset of npermutations represented as 0/1 matrices We present a linear system that models the coNPcomplete nonHamilton 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 n1 by n1 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 Fn 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 nonHamilton tour decision problem is modeled by Fn such that G n is nonHamiltonian if and only if under an orthogonal projection the image of the solution set of Fn is P n −1 The decision problem ‘Is the projection of the solution set of Fn=P n −1’ is therefore coNPcomplete and this particular model of the nonHamilton tour problem appears to be new
Keywords: