The Traveling Salesman Problem in Circulant Weighted Graphs With Two Stripes

The Symmetric Circulant Traveling Salesman Problem asks for the minimum cost of a Hamiltonian cycle in a circulant weighted undirected graph. The computational complexity of this problem is not known. Just a constructive upper bound, and a good lower bound have been determined. This paper provides a characterization of the two stripe case. Instances where the minimum cost of a Hamiltonian cycle is equal either to the upper bound, or to the lower bound are recognized. A new construction providing Hamiltonian cycles, whose cost is in many cases lower than the upper bound, is proposed for the remaining instances.