Page 625 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 625
COMBINATORICS AND DISCRETE MATHEMATICS
n. These tours are of interest, since, on the one hand, the minimum cost tour can be determined
in O(n2) time by dynamic programming, and, on the other hand, there are known restrictions
on the distance matrix that guarantee the existence of an optimal solution that is a pyramidal
tour with step-backs.
We define the traveling salesperson polytope TSP(n) and the polytope of pyramidal tours
with step-backs PSB(n) as the convex hulls of characteristic vectors of all corresponding tours
in the complete digraph Kn. It is known that for the polytope TSP(n) the question of whether
two vertices are nonadjacent is NP-complete [4], the diameter equals 2 for asymmetric poly-
tope [3] and is at most 4 for symmetric polytope [5], and the clique number of 1-skeleton is
superpolynomial in n [1].
Let x and y be two pyramidal tours with step-backs. We denote by xv and yv the correspond-
ing vertices of the PSB(n) polytope and by x ∪ y a regular directed multigraph that contains all
edges of both tours x and y.
Lemma 1 (Sufficient condition for nonadjacency). Given two tours x and y, if the multigraph
x ∪ y includes a pair of edge-disjoint pyramidal tours with step-backs, different from x and y,
then the corresponding vertices xv and yv of the polytope PSB(n) are not adjacent.
Lemma 2 (Necessary condition for nonadjacency). If the vertices xv and yv of the polytope
PSB(n) are not adjacent, then the multigraph x ∪ y includes at least two pyramidal tours with
step-backs, different from x and y.
Our main result is that both necessary and sufficient conditions for nonadjacency can be
verified in linear time.
Theorem 1. The question of whether two vertices of the polytope PSB(n) are adjacent or
nonadjacent can be verified in linear time O(n).
Based on the vertex adjacency relation, we can investigate other characteristics of 1-skeleton
of the polytope PSB(n).
Theorem 2. The diameter of 1-skeleton of the polytope PSB(n) is bounded above by 4. The
clique number of 1-skeleton of the polytope PSB(n) is quadratic in n:
ω(PSB(n)) = Θ(n2).
Thus, the polyhedral characteristics of the traveling salesperson problem on Hamiltonian
cycles and pyramidal tours with step-backs are fundamentally different and correspond to the
computational complexity of the problem.
References
[1] Bondarenko V. A., Nonpolynomial lower bounds for the complexity of the traveling sales-
man problem in a class of algorithms, Autom. Remote Control, 44 (1983), 1137–1142.
[2] Enomoto H., Oda Y., Ota K., Pyramidal tours with step-backs and the asymmetric travel-
ing salesman problem, Discrete Appl. Math., 87 (1998) 57–65.
[3] Padberg M. W., Rao M. R., The travelling salesman problem and a class of polyhedra of
diameter two, Math. Program., 7 (1974), 32–45.
[4] Papadimitriou C. H., The adjacency relation on the traveling salesman polytope is NP-
Complete, Math. Program., 14 (1978), 312–324.
623
n. These tours are of interest, since, on the one hand, the minimum cost tour can be determined
in O(n2) time by dynamic programming, and, on the other hand, there are known restrictions
on the distance matrix that guarantee the existence of an optimal solution that is a pyramidal
tour with step-backs.
We define the traveling salesperson polytope TSP(n) and the polytope of pyramidal tours
with step-backs PSB(n) as the convex hulls of characteristic vectors of all corresponding tours
in the complete digraph Kn. It is known that for the polytope TSP(n) the question of whether
two vertices are nonadjacent is NP-complete [4], the diameter equals 2 for asymmetric poly-
tope [3] and is at most 4 for symmetric polytope [5], and the clique number of 1-skeleton is
superpolynomial in n [1].
Let x and y be two pyramidal tours with step-backs. We denote by xv and yv the correspond-
ing vertices of the PSB(n) polytope and by x ∪ y a regular directed multigraph that contains all
edges of both tours x and y.
Lemma 1 (Sufficient condition for nonadjacency). Given two tours x and y, if the multigraph
x ∪ y includes a pair of edge-disjoint pyramidal tours with step-backs, different from x and y,
then the corresponding vertices xv and yv of the polytope PSB(n) are not adjacent.
Lemma 2 (Necessary condition for nonadjacency). If the vertices xv and yv of the polytope
PSB(n) are not adjacent, then the multigraph x ∪ y includes at least two pyramidal tours with
step-backs, different from x and y.
Our main result is that both necessary and sufficient conditions for nonadjacency can be
verified in linear time.
Theorem 1. The question of whether two vertices of the polytope PSB(n) are adjacent or
nonadjacent can be verified in linear time O(n).
Based on the vertex adjacency relation, we can investigate other characteristics of 1-skeleton
of the polytope PSB(n).
Theorem 2. The diameter of 1-skeleton of the polytope PSB(n) is bounded above by 4. The
clique number of 1-skeleton of the polytope PSB(n) is quadratic in n:
ω(PSB(n)) = Θ(n2).
Thus, the polyhedral characteristics of the traveling salesperson problem on Hamiltonian
cycles and pyramidal tours with step-backs are fundamentally different and correspond to the
computational complexity of the problem.
References
[1] Bondarenko V. A., Nonpolynomial lower bounds for the complexity of the traveling sales-
man problem in a class of algorithms, Autom. Remote Control, 44 (1983), 1137–1142.
[2] Enomoto H., Oda Y., Ota K., Pyramidal tours with step-backs and the asymmetric travel-
ing salesman problem, Discrete Appl. Math., 87 (1998) 57–65.
[3] Padberg M. W., Rao M. R., The travelling salesman problem and a class of polyhedra of
diameter two, Math. Program., 7 (1974), 32–45.
[4] Papadimitriou C. H., The adjacency relation on the traveling salesman polytope is NP-
Complete, Math. Program., 14 (1978), 312–324.
623
