On Pedigree Polytopes and Hamiltonian Cycles

Polyhedral combinatorics deals with solving combinatorial optimisation problems using the polytope whose vertices are the characteristic vectors of the combinatorial objects of interest. Given the complete graph with n vertices, Kn, with rational edge weights, the symmetric travelling salesman problem (STSP) is to find a Hamiltonian cycle such that the total edge weight of the Hamiltonian cycle is as small as possible. Polyhedral approach to solve STSP, starts with the standard tour poly-tope, Qn, whose vertices are the characteristic vectors of Hamiltonian cycles, and given a point from a polytope, P containing Qn, it tries to find a separating hyperplane that separates the point and Qn or shows that the point is in Qn. In this paper we define a combinatorial object called pedigree, and study an alternative polytope, called Pedigree polytope. Pedigrees are in one-to-one correspondence with the Hamiltonian cycles on Kn. Interestingly the pedigree polytope seems to differ from Qn with respect to the complexity of testing whether two given vertices of the polytope are non-adjacent. A polynomial time algorithm is given for non-adjacency testing in pedigree polytope, whereas the corresponding problem is known to be NP-complete for Qn. In this paper we discuss some properties of the pedigree polytope and illustrate with examples.