Volume 25, No 1, 2018, P. 5-24

UDC 519.16+514.172.45
V. A. Bondarenko and A. V. Nikolaev
On the skeleton of the polytope of pyramidal tours

Abstract:
We consider the skeleton of the polytope of pyramidal tours. A Hamiltonian tour is called pyramidal if the salesperson starts in city 1, then visits some cities in increasing order of their numbers, reaches city $n$, and returns to city 1 visiting the remaining cities in decreasing order. The polytope PYR($n$) is defined as the convex hull of the characteristic vectors of all pyramidal tours in the complete graph $K_n$. The skeleton of PYR($n$) is the graph whose vertex set is the vertex set of PYR($n$) and the edge set is the set of geometric edges or one-dimensional faces of PYR($n$). We describe the necessary and sufficient condition for the adjacency of vertices of the polytope PYR($n$). On this basis we developed an algorithm to check the vertex adjacency with linear complexity. We establish that the diameter of the skeleton of PYR($n$) equals 2, and the asymptotically exact estimate of the clique number of the skeleton of PYR($n$) is $\Theta (n^2)$. It is known that this value characterizes the time complexity in a broad class of algorithms based on linear comparisons.
Illustr. 4, bibliogr. 23.

Keywords: pyramidal tour, 1-skeleton, necessary and sufficient condition of adjacency, clique number, graph diameter.

DOI: 10.17377/daio.2018.25.570

Vladimir A. Bondarenko ¹
Andrei V. Nikolaev ¹
1. Demidov Yaroslavl State University,
14 Sovetskaya St., 150003 Yaroslavl, Russia
e-mail: bond@bond.edu.yar.ru, andrei.v.nikolaev@gmail.com

Received 3 March 2017

References

[1] V. S. Aizenshtat and D. N. Kravchuk, On the minimum of a linear form on the set of all cycles of the symmetric group Sn, Kibern., 2, 64–66, 1968 [Russian]. Translated in Cybern., 4, 52–53, 1968.

[2] Yu. A. Belov, On clique number of the matroid graph, Modeli issledovaniya operatsii v vychislitel’nykh sistemakh (Operations Research Models in Computing Systems), pp. 95–100, Yarosl. Gos. Univ., Yaroslavl, 1985 [Russian].

[3] V. A. Bondarenko, Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms, Avtom. Telemekh., No. 9, 44–50, 1983 [Russian]. Translated in Autom. Remote Control, 44, No. 9, 1137–1142, 1983.

[4] V. A. Bondarenko and A. N. Maksimenko, Geometricheskie konstruktsii i slozhnost’ v kombinatornoi optimizatsii (Geometric constructions and complexity in combinatorial optimization), LKI, Moscow, 2008 [Russian].

[5] V. A. Bondarenko, A. V. Nikolaev, and D. A. Shovgenov, 1-skeletons of the spanning tree problems with additional constraints, Model. Anal. Inf. Syst., 22, No. 9, 453–463, 2015 [Russian].

[6] P. S. Klyaus, Generation of testproblems for the traveling salesman problem, Prepr. Inst. Mat. Akad. Nauk BSSR, No. 16, Inst. Mat. AN BSSR, Minsk, 1976 [Russian].

[7] D. L. Applegate, R. E. Bixby, V. Chvátal, and W. J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton Univ. Press, Princeton, NJ, 2007.

[8] V. A. Bondarenko and A. V. Nikolaev, On graphs of the cone decompositions for the min-cut and max-cut problems, Int. J. Math. Math. Sci., 2016, 1–6, 2016.

[9] V. A. Bondarenko and A. V. Nikolaev, On the skeleton of the pyramidal tours polytope, in Abstr. 17th Baikal Int. Sch. Semin. Conf. “Methods of Optimization and Their Applications”, Irkutsk, Russia, July 31 – Aug. 6, 2017, p. 84, ESI SB RAS, Irkutsk, 2017.

[10] V. A. Bondarenko and A. V. Nikolaev, Some properties of the skeleton of the pyramidal tours polytope, Electron. Notes Discrete Math., 61, 131–137, 2017.

[11] R. E. Burkard, V. G. Deineko, R. van Dal, J. A. A. van der Veen, and G. J. Woeginger, Well-solvable special cases of the traveling salesman problem: A survey, SIAM Rev., 40, No. 3, 496–546, 1998.

[12] G. Dantzig, R. Fulkerson, and S. Johnson, Solution of a large scale traveling salesman problem, Tech. Rep. P-510, RAND Corp., Santa Monica, CA, 1954.

[13] V. G. Deineko, B. Klinz, A. Tiskin, and G. J. Woeginger, Four-point conditions for the TSP: The complete complexity classification, Discrete Optim., 14, 147–159, 2014.

[14] D. Geist and E. Y. Rodin, Adjacency of the 0–1 knapsack problem, Comput. Oper. Res., 19, No. 8, 797–800, 1992.

[15] P. C. Gilmore, E. L. Lawler, and D. B. Shmoys, Well-solved special cases, in The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, pp. 87–143, Wiley, Chichester, UK, 1985.

[16] E. Girlich, M. Höding, A. Horbach, and M. Kovalev, On the facets and diameter of the $k$-cycle polytope, Optim., 55, No. 4, 311–339, 2006.

[17] M. Grötschel and M. Padberg, Polyhedral theory, in The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, pp. 251–305, Wiley, Chichester, UK, 1985.

[18] M. W. Padberg and M. R. Rao, The travelling salesman problem and a class of polyhedra of diameter two, Math. Program., 7, No. 1, 32–45, 1974.

[19] C. H. Papadimitriou, The adjacency relation on the traveling salesman polytope is NP-complete, Math. Program., 14, No. 1, 312–324, 1978.

[20] F. J. Rispoli and S. Cosares, A bound of 4 for the diameter of the symmetric traveling salesman polytope, SIAM J. Discrete Math., 11, No. 3, 373–380, 1998.

[21] G. Sierksma, The skeleton of the symmetric traveling salesman polytope, Discrete Appl. Math., 43, No. 1, 63–74, 1993.

[22] G. Sierksma, R. H. Teunter, and G. A. Tijssen, Faces of diameter two on the Hamiltonian cycle polytype, Oper. Res. Lett., 18, No. 2, 59–64, 1995.

[23] G. Sierksma and G. A. Tijssen, Faces with large diameter on the symmetric traveling salesman polytope, Oper. Res. Lett., 12, No. 2, 73–77, 1992.