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.
