Traveling Salesman

Input

Set $C$ of $m$ cities, distance $d(c_i, c_j) \in \mathbb{Z}^{+}$ for each pair of cities $c_i, c_j \in C$, positive integer $B$.

Question

Is there a tour of $C$ having length $B$ or less, i.e. a permutation $<c_{\pi(1)}, c_{\pi(2)}, \dots, c_{\pi(m)}>$ of $C$ such that $\left(\sum_{i = 1}^{m-1} d(c_{\pi(i)}, c_{\pi(i+1)})\right) + d(c_{\pi(m)}, c_{\pi(1)}) \leq B$?

Classes

• NP-complete

Comments

Remains NP-complete even if $d(c_i, c_j) \in \{1, 2\}$ for all $c_i, c_j \in C$. Special cases that can be solved in polynomial time are discussed in (Gilmore & Gomory, 1964), (Garfinkel, 1977) and (Sysło, 1973). The variant in which we ask for a tour with mean arrival time of $B$ or less is also NP-complete (Sahni & Gonzalez, 1976).

Proofs

NP-complete

Transformation from Hamiltonian Circuit.

Reducible from

• Hamiltonian Circuit

References

• Gilmore, P. C., & Gomory, R. E. (1964). Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem. Operations Research, 12(5), 655–679. https://doi.org/10.1287/opre.12.5.655
• Garfinkel, R. S. (1977). Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems. Operations Research, 25(5), 741–751. https://doi.org/10.1287/opre.25.5.741
• Sysło, M. M. (1973). A new solvable case of the traveling salesman problem. Mathematical Programming, 4(1), 347–348. https://doi.org/10.1007/bf01584676
• Sahni, S., & Gonzalez, T. (1976). P-Complete Approximation Problems. Journal of the ACM, 23(3), 555–565. https://doi.org/10.1145/321958.321975