On pedigree polytopes and Hamiltonian cycles

In this paper we define a combinatorial object called a pedigree, and study the corresponding polytope, called the pedigree polytope. Pedigrees are in one-to-one correspondence with the Hamiltonian cycles on KnKn. Interestingly, the pedigree polytope seems to differ from the standard tour polytope, QnQn with respect to the complexity of testing whether two given vertices of the polytope are nonadjacent. A polynomial time algorithm is given for nonadjacency testing in the pedigree polytope, whereas the corresponding problem is known to be NP  -complete for QnQn. We also discuss some properties of the pedigree polytope and illustrate with examples.