Geodesic
On $1$-skeleton of the polytope of pyramidal tours with step-backs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 674-687.

Voir la notice de l'article provenant de la source Math-Net.Ru

Pyramidal tours with step-backs are Hamiltonian tours of a special kind: the salesperson starts in city $1$, then visits some cities in ascending order, reaches city $n$, and returns to city $1$ visiting the remaining cities in descending order. However, in the ascending and descending direction, the order of neighboring cities can be inverted (a step-back). It is known that on pyramidal tours with step-backs the traveling salesperson problem can be solved by dynamic programming in polynomial time. We define the polytope of pyramidal tours with step-backs $\mathrm{PSB}(n)$ as the convex hull of the characteristic vectors of all possible pyramidal tours with step-backs in a complete directed graph. The $1$-skeleton of $\mathrm{PSB}(n)$ is the graph whose vertex set is the vertex set of the polytope, and the edge set is the set of geometric edges or one-dimensional faces of the polytope. We present a linear-time algorithm to verify vertex adjacency in the $1$-skeleton of the polytope $\mathrm{PSB}(n)$ and estimate the diameter and the clique number of the $1$-skeleton: the diameter is bounded above by $4$ and the clique number grows quadratically in the parameter $n$.
Keywords: pyramidal tour with step-backs, $1$-skeleton, vertex adjacency, graph diameter, clique number, pyramidal encoding. 
@article{SEMR_2022_19_2_a33,
     author = {A. V. Nikolaev},
     title = {On $1$-skeleton of the polytope of pyramidal tours with step-backs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {674--687},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a33/}
}
TY  - JOUR
AU  - A. V. Nikolaev
TI  - On $1$-skeleton of the polytope of pyramidal tours with step-backs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2022
SP  - 674
EP  - 687
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a33/
LA  - en
ID  - SEMR_2022_19_2_a33
ER  - 
%0 Journal Article
%A A. V. Nikolaev
%T On $1$-skeleton of the polytope of pyramidal tours with step-backs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2022
%P 674-687
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a33/
%G en
%F SEMR_2022_19_2_a33
A. V. Nikolaev. On $1$-skeleton of the polytope of pyramidal tours with step-backs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 674-687. http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a33/

[1] V. Aĭzenshtat, D. Kravchuk, “On the minimum of a linear form on the set of all complete cycles of the symmetric group $S_n$”, Kibernetika, 2, Kiev, 1968, 64–66 | MR | Zbl

[2] D.L. Applegate, R.E. Bixby, V. Chvátal, W.J. Cook, The traveling salesman problem. A computational study, Princeton University Press, Princeton, 2006 | MR | Zbl

[3] T. Arthanari, “Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope”, Discrete Optim., 10:3 (2013), 224–232 | DOI | MR | Zbl

[4] E. Balas, M. Padberg, “On the set-covering problem. II: An algorithm for set partitioning”, Oper. Res., 23:1 (1975), 74–90 | DOI | MR | Zbl

[5] M.L. Balinski, “Signature methods for the assignment problem”, Oper. Res., 33:3 (1985), 527–536 | DOI | MR | Zbl

[6] V. Bondarenko, A. Nikolaev, “On graphs of the cone decompositions for the min-cut and max-cut problems”, Int. J. Math. Math. Sci., 2016, 7863650 | MR | Zbl

[7] V. Bondarenko, A. Nikolaev, “Some properties of the skeleton of the pyramidal tours polytope”, Electronic Notes Discrete Math., 61 (2017), 131–137 | DOI | Zbl

[8] V.A. Bondarenko, “Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms”, Autom. Remote Control, 44:9 (1983), 1137–1142 | MR | Zbl

[9] V.A. Bondarenko, A.V. Nikolaev, “Combinatorial and geometric properties of the max-cut and min-cut problems”, Dokl. Math., 88:2 (2013), 516–517 | DOI | MR | Zbl

[10] V.A. Bondarenko, A.V. Nikolaev, D.A. Shovgenov, “1-skeletons of the spanning tree problems with additional constraints”, Autom. Control Comput. Sci., 51:7 (2017), 682–688 | DOI

[11] V.A. Bondarenko, A.V. Nikolaev, “On the skeleton of the polytope of pyramidal tours”, J. Appl. Ind. Math., 12:1 (2018), 9–18 | DOI | MR | Zbl

[12] R.E. Burkard, V.G. Deineko, R. van Dal, J.A.A. van der Veen, G.J. Woeginger, “Well-solvable special cases of the traveling salesman problem: a survey”, SIAM Rev., 40:3 (1998), 496–546 | DOI | MR | Zbl

[13] G. Dantzig, R. Fulkerson, S. Johnson, “Solution of a large-scale traveling-salesman problem”, Oper. Res., 2:4 (1954), 393–410 | MR | Zbl

[14] G.B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, 1963 | MR | Zbl

[15] J. Edmonds, “Paths, trees, and flowers”, Can. J. Math., 17 (1965), 449–467 | DOI | MR | Zbl

[16] H. Enomoto, Y. Oda, K. Ota, “Pyramidal tours with step-backs and the asymmetric traveling salesman problem”, Discrete Appl. Math., 87:1-3 (1998), 57–65 | DOI | MR | Zbl

[17] M.R. Garey, D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W.H. Freeman, San Francisco, 1979 | MR | Zbl

[18] P. Gilmore, E. Lawler, D. Shmoys, “Well-solved special cases”, The traveling salesman problem. A guided tour of combinatorial optimization, eds. E. Lawler et al, John Wiley Sons, Chichester etc, 1985, 87–143 | MR | Zbl

[19] M. Grötschel, M. Padberg, “Polyhedral theory”, The traveling salesman problem. A guided tour of combinatorial optimization, eds. E. Lawler et al, John Wiley Sons, Chichester etc, 1985, 251–305 | MR | Zbl

[20] Y. Ikura, G.L. Nemhauser, “Simplex pivots on the set packing polytope”, Math. Program., 33 (1985), 123–138 | DOI | MR | Zbl

[21] S.N. Kabadi, “Polynomially solvable cases of the TSP”, The traveling salesman problem and its variations, eds. Gutin Gregory (ed.) et al., Kluwer Academic Publishers, Dordrecht, 2007, 489–583 | DOI | MR | Zbl

[22] M. Khachay, K. Neznakhina, “Generalized pyramidal tours for the generalized traveling salesman problem”, Combinatorial optimization and applications, 11th international conference, COCOA 2017, Proceedings (Shanghai, China, December 16-18, 2017), v. I, eds. Gao Xiaofeng (ed.) et al., Springer, Cham, 2017, 265–277 | DOI | MR | Zbl

[23] P.S. Klyaus, Generation of testproblems for the traveling salesman problem, Prperint Inst. Mat. Akad. Nauk. BSSR, No 16, 1976 | MR

[24] A. Nikolaev, “On vertex adjacencies in the polytope of pyramidal tours with step-backs”, Mathematical optimization theory and operations research, 18th international conference, MOTOR 2019, Proceedings (Ekaterinburg, Russia, July 8-12, 2019), LNCS, 11548, eds. Khachay Michael (ed.) et al., Springer, Cham, 2019, 247–263 | MR | Zbl

[25] A. Nikolaev, A. Kozlova, “Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search”, J. Comb. Optim., 42:2 (2021), 212–230 | DOI | MR | Zbl

[26] Y. Oda, “An asymmetric analogue of van der Veen conditions and the traveling salesman problem”, Discrete Appl. Math., 109:3 (2001), 279–292 | DOI | MR | Zbl

[27] M.W. Padberg, M.R. Rao, “The travelling salesman problem and a class of polyhedra of diameter two”, Math. Program., 7:1 (1974), 32–45 | DOI | MR | Zbl

[28] C.H. Papadimitriou, “The adjacency relation on the traveling salesman polytope is NP-complete”, Math. Program., 14:1 (1978), 312–324 | DOI | MR | Zbl

[29] F.J. Rispoli, S. Cosares, “A bound of 4 for the diameter of the symmetric traveling salesman polytope”, SIAM J. Discrete Math., 11:3 (1998), 373–380 | DOI | MR | Zbl

[30] F. Santos, “A counterexample to the Hirsch conjecture”, Ann. Math. (2), 176:1 (2012), 383–412 | DOI | MR | Zbl

[31] G. Sierksma, R.H. Teunter, G.A. Tijssen, “Faces of diameter two on the Hamiltonian cycle polytype”, Oper. Res. Lett., 18:2 (1995), 59–64 | DOI | MR | Zbl

[32] R.Y. Simanchev, “On the vertex adjacency in a polytope of connected k-factors”, Trudy Inst. Mat. Mekh. UrO RAN, 24, no. 2, 2018, 235–242 | DOI | MR