  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.
