On Pedigree Polytopes and Hamiltonian Cycles

Abstract

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, K, 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, Q, whose vertices are the characteristic vectors of Hamiltonian cycles, and given a point from a polytope, P containing Q, it tries to find a separating hyperplane that separates the point and Q or shows that the point is in Q. 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 K. Interestingly the pedigree polytope seems to differ from Q 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 Q. In this paper we discuss some properties of the pedigree polytope and illustrate with examples.