Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable
- PDF / 625,813 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 34 Downloads / 195 Views
Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search Andrei Nikolaev1
· Anna Kozlova1
Accepted: 18 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. A sufficient condition for vertex adjacency in the 1-skeleton of the traveling salesperson polytope can be formulated as the Hamiltonian decomposition problem in a 4-regular multigraph. We introduce a heuristic general variable neighborhood search algorithm for this problem based on finding a vertex-disjoint cycle cover of the multigraph through reduction to perfect matching and several cycle merging operations. The algorithm has a one-sided error: the answer “not adjacent” is always correct, and was tested on random directed and undirected Hamiltonian cycles and on pyramidal tours. Keywords Hamiltonian decomposition · Traveling salesperson polytope · 1-skeleton · Vertex adjacency · General variable neighborhood search · Variable neighborhood descent · Vertex-disjoint cycle cover · Perfect matching
1 Introduction A Hamiltonian decomposition of a regular graph is a partition of its edge set into Hamiltonian cycles. The problem of finding edge-disjoint Hamiltonian cycles in a given regular graph plays an important role in combinatorial optimization (Krarup 1995), coding theory (Bae and Bose 2003; Bailey 2009), privacy-preserving distributed min-
The research is supported by the Grant of the President of the Russian Federation MK-2620.2018.1 (Agreement No. 075-015-2019-746).
B
Andrei Nikolaev [email protected] Anna Kozlova [email protected]
1
P. G. Demidov Yaroslavl State University, Yaroslavl, Russia
123
Journal of Combinatorial Optimization
ing algorithms (Clifton et al. 2002), analysis of interconnection networks (Hung 2011) and other areas. See also theoretical results on estimating the number of Hamiltonian decompositions of regular graphs (Glebov et al. 2017). Our motivation for this problem comes from the field of polyhedral combinatorics.
2 Traveling salesperson polytope We consider a classic traveling salesperson problem: given a complete weighted graph (or digraph) K n = (V , E), it is required to find a Hamiltonian cycle of minimum weight. We denote by H Cn the set of all Hamiltonian cycles in K n . With each Hamiltonian cycle x ∈ H Cn we associate a characteristic vector x v ∈ R E by the following rule: 1, if the cycle x contains an edge e ∈ E, v xe = 0, otherwise. The polytope TSP(n) = conv{x v | x ∈ H Cn } is called the symmetric traveling salesperson polytope. The asymmetric traveling salesperson polytope ATSP(n) is defined similarly as the convex hull of characteristic vectors of all possible Hamiltonian cycles in the complete digraph K n . The 1-skeleton of a polytope P is the graph whose vertex set is the vertex set of P and edge set is the set of geometric edges or one-dimensional faces
Data Loading...
