On vertex adjacencies in the polytope of pyramidal tours with step-backs

Abstract

We consider the traveling salesperson problem in a directed graph. The pyramidal tours with step-backs are a special class of Hamiltonian cycles for which the traveling salesperson problem is solved by dynamic programming in polynomial time. The polytope of pyramidal tours with step-backs $PSB(n)$ is defined as the convex hull of the characteristic vectors of all possible pyramidal tours with step-backs in a complete directed graph. The skeleton of $PSB(n)$ is the graph whose vertex set is the vertex set of $PSB(n)$ and the edge set is the set of geometric edges or one-dimensional faces of $PSB(n)$. The main result of the paper is a necessary and sufficient condition for vertex adjacencies in the skeleton of the polytope $PSB(n)$ that can be verified in polynomial time.

in English