Computational Complexity of the Symmetric Circulant Traveling Salesman Problem

The symmetric circulant Traveling Salesman Problem (TSP) restricts the TSP to instances whose cost matrix is a symmetric circulant matrix: the cost of an edge depends only on the circular distance between its endpoints, so an n-city instance is described by just n and its ⌊n/2⌋ nonnegative costs, one per edge length ("stripe"). Whether this problem is solvable in polynomial time or is NP-hard has been open for decades and is repeatedly cited as a major open question on the boundary between tractable and intractable TSP special cases. Known results leave the question untouched: a 2-approximation exists, the subtour LP (the subtour-elimination linear programming relaxation of the TSP) has integrality gap — the worst-case ratio between the true optimal tour cost and the LP bound — exactly 2 on circulant instances, and neither the recently proven circulant facet inequalities nor any known strengthened relaxation pushes the gap below 2. The two-stripe special case (only two stripes with finite cost) was resolved in 2022 — it is in P — but the complexity of the general problem, open already when any constant number k ≥ 3 of stripes have finite cost, remains unresolved in the most recent literature (2025).

Background

The Traveling Salesman Problem (TSP) asks for a minimum-cost Hamiltonian cycle, i.e., a closed tour visiting each of $n$ vertices exactly once, in a complete graph whose edges have given costs. The TSP is NP-hard in general, which motivates studying structured special cases. An instance is circulant when the cost of an edge $\{i,j\}$ depends only on its circular length $\min(|i-j|,\;n-|i-j|)$: the cost matrix is then a symmetric circulant matrix (each row is a cyclic shift of the previous one), and the entire instance is specified by $n$ together with $d=\lfloor n/2\rfloor$ nonnegative costs $c_1,\dots,c_d$. Edges of circular length $k$ are said to form the $k$-th stripe; all edges in a stripe share the cost $c_k$. The input is thus compressed from $\Theta(n^2)$ arbitrary costs to $\Theta(n)$ parameters, and the costs need not satisfy the triangle inequality.

Circulant instances sit precisely on the boundary between easy and hard. As surveyed by Gutekunst and Williamson (2019), several classic problems become polynomial-time solvable under circulant symmetry — deciding whether a symmetric circulant graph is Hamiltonian, the bottleneck version of the TSP on circulant graphs, and finding minimum-cost Hamiltonian paths in circulant graphs — while other NP-hard problems, such as Max Clique and Graph Coloring, remain NP-hard even restricted to circulant graphs. Because of this ambiguity, the complexity of the circulant TSP itself has been cited as an open problem for decades, including in standard surveys of well-solvable TSP special cases. Some subcases are easy: when the cheapest stripe has length relatively prime to $n$ (for example whenever $n$ is prime), following edges of the cheapest stripe yields an optimal tour. In general, a 2-approximation algorithm is known, based on heuristics that exploit only the ordering of the stripe costs.

The main structural result about this class concerns the subtour LP, the subtour-elimination linear programming relaxation of the TSP (also known as the Dantzig–Fulkerson–Johnson relaxation or the Held–Karp bound), in which the requirement that each edge be used 0 or 1 times is relaxed to allow fractional values while every vertex keeps degree 2 and every cut is crossed at least twice. Gutekunst and Williamson (2019) proved that on circulant instances the subtour LP optimum equals an explicit combinatorial lower bound and that its integrality gap — the worst-case ratio between the true optimum and the LP optimum — is exactly 2. Since the known 2-approximation matches this LP guarantee, current relaxation-based tools give no traction toward exact tractability. The same paper showed that adding known facet-defining inequalities (an inequality is facet-defining if it cannot be strengthened without cutting off some valid tour) — the crown, ladder, and chain inequalities — does not reduce the gap below 2 on circulant instances, and conjectured a new family of circulant inequalities (its Conjecture 5.2).

Subsequent work resolved parts of this landscape. The conjectured inequalities were proven valid and facet-defining as the circlet inequalities (Gutekunst and Williamson, 2023), though their strength matches the worst case of the crown inequalities and no strengthened polynomial-time relaxation with integrality gap below 2 on circulant instances is known. The two-stripe case — only two stripe costs finite — was proven polynomial-time solvable by Gutekunst, Jin, and Williamson (2022) via a reduction to minimum-cost Hamiltonian paths on cylindrical graphs. A natural algorithmic route is the edge-length polytope, whose points record how many edges of each length a tour uses; because circulant costs depend only on lengths, optimizing over it would solve the problem, but its number of vertices depends on the factorization of $n$ and is superpolynomial when $n$ is a power of 2 (Gutekunst, 2025), blocking enumeration-based algorithms in the worst case. What remains unresolved is the question that Gutekunst and Williamson (2019) call a decades-long major open question: the complexity classification of the general problem.

Problem Statement

An instance of the symmetric circulant TSP is given by an integer $n\ge3$ and nonnegative costs $c_1,\dots,c_d$ with $d=\lfloor n/2\rfloor$: the vertices are $1,\dots,n$, and the cost of the edge $\{i,j\}$ between distinct vertices $i,j$ is $c_{\min(|i-j|,\;n-|i-j|)}$, so all edges of the same circular length (the same stripe) share one cost. The task is to compute a minimum-cost Hamiltonian cycle of the complete graph on these vertices.

Question: is the symmetric circulant TSP solvable in polynomial time in the length of its input (the bit encodings of $n$ and of $c_1,\dots,c_d$), or is it NP-hard — where NP-hardness is asked of the decision version: given additionally a bound $B$, decide whether some tour has cost at most $B$?

The question is open for the general case in which all stripe costs are finite, and is open already when any fixed constant number $k\ge3$ of the stripe costs are finite and the remaining stripe costs are infinite (effectively arbitrarily large). The two-stripe case $k=2$, which Gutekunst and Williamson (2019) highlighted as open, was resolved in 2022 (it is in P), so the surviving open core is the complexity classification above, for $k\ge3$ finite stripes and for the fully general problem. Resolving the complexity classification for the fully general problem (all stripe costs finite) resolves the task; the fixed-$k\ge3$ case is an additional restricted family whose classification is also open. No restriction on the cost pattern (metric or non-metric, distinct or repeated costs) may be assumed.

References

1. Samuel C. Gutekunst and David P. Williamson. Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem. SIAM Journal on Discrete Mathematics, 33:2452–2478, 2019. DOI: 10.1137/19m1245840 (arXiv:1902.06808). https://doi.org/10.1137/19m1245840
2. Samuel C. Gutekunst and David P. Williamson. The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP. Mathematics of Operations Research, 48:393–418, 2023. DOI: 10.1287/moor.2022.1265 (arXiv:2012.12363). https://doi.org/10.1287/moor.2022.1265
3. Samuel C. Gutekunst, Billy Jin, and David P. Williamson. The two-stripe symmetric circulant TSP is in P. Mathematical Programming, 215(1–2):95–143, 2026 (online first 2025). DOI: 10.1007/s10107-025-02215-2 (arXiv:2207.10254). https://doi.org/10.1007/s10107-025-02215-2
4. Samuel C. Gutekunst. Circulant TSP: Vertices of the edge-length polytope and superpolynomial lower bounds. Discrete Applied Mathematics, 376:208–224, 2025. DOI: 10.1016/j.dam.2025.06.013 (arXiv:2506.10758). https://doi.org/10.1016/j.dam.2025.06.013