Skip to main content
SpringerLink
Log in

The adjacency relation on the traveling salesman polytope is NP-Complete

  • Published:
Mathematical Programming Submit manuscript

Abstract

We consider the problem of determining whether two traveling salesman tours correspond to non-adjacent vertices of the convex polytope associated with the traveling salesman problem. This problem is shown to be NP-Complete for both the symmetric and nonsymmetric traveling salesman problem. Several implications are discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A.V. Aho, J.E. Hopcroft and J.D. Ullman,The design and analysis of computer algorithms (Addison-Wesley, Reading, MA, 1974).

    Google Scholar 

  2. E. Balas, “Facets of the knapsack polytope”,Mathematical Programming 8(2) (1975) 146–164.

    Google Scholar 

  3. M. Bellmore and G.L. Nemhauser, “The traveling salesman problem: a survey”,Operations Research 16 (1968) 538–558.

    Google Scholar 

  4. V. Chvatal, “On certain polytopes associated with graphs”,Journal of Combinatorial Theory 18B (1975) 138–154.

    Google Scholar 

  5. J. Edmonds, “Matroids and the greedy algorithm”,Mathematical Programming 1 (1971) 127–136.

    Google Scholar 

  6. M.R. Garey, D.S. Johnson and I. Stockmeyer, “Some simplified NP-complete problems”,Proceedings 6th SIGACT symposium on the theory of computing, (1974) pp. 47–63.

  7. M.R. Garey, D.S. Johnson and R.E. Tarjan, “The planar Hamiltonian circuit problem is NP-complete”,SIAM Journal on Computing 5(4) (1976) 704–714.

    Google Scholar 

  8. B. Grünbaum,Convex polytopes (Interscience, 1967).

  9. R.M. Karp, “Reducibility among combinatorial problems”, in: R.E. Miller and J.W. Thatcher, eds.,Complexity of computer computations (Plenum, New York, 1972) pp. 85–103.

    Google Scholar 

  10. R.M. Karp, “On the computational complexity of combinatorial problems”,Networks 5 (1975) 45–68.

    Google Scholar 

  11. S. Lin, “Computer solutions of the traveling salesman problem”,Bell System Technical Journal 44 (1965) 2245–2269.

    Google Scholar 

  12. S. Lin and B.W. Kernighan, “An effective heuristic algorithm for the traveling salesman problem”,Operations Research 21(2) (1973) 498–515.

    Google Scholar 

  13. K.G. Murty, “On the tours of a traveling salesman”,SIAM Journal on Control 7 (1969) 122–131.

    Google Scholar 

  14. K.G. Murty, “A fundamental problem in linear inequalities with applications to the traveling salesman problem”,Mathematical Programming 2(3) (1972) 296–308.

    Google Scholar 

  15. M.W. Padberg and M.R. Rao, “The traveling salesman problem and a class of polyhedra of diameter two”,Mathematical Programming 7(1) (1974) 32–45.

    Google Scholar 

  16. C.H. Papadimitriou and K. Steiglitz, “On the complexity of local search for the traveling salesman problem”,SIAM Journal of Computing 6(1) (1977) 76–83.

    Google Scholar 

  17. C.H. Papadimitriou, “The euclidean traveling salesman problem is NP-complete”,Theoretical Computer Science 4(3) (1977) 237–244.

    Google Scholar 

  18. M.R. Rao, “Adjacency of the traveling salesman tours and 0–1 vertices”,SIAM Journal on Applied Mathematics 30(2) (1976) 191–198.

    Google Scholar 

  19. S. Sahni, T. Gonzalez, “P-complete problems and approximate solutions”,Journal of the Association for Computing Machinery, 23(3) (1976) 555–566.

    Google Scholar 

  20. M. Simmonard,Linear programming (Prentice Hall, Englewood Cliffs, NJ, 1966).

    Google Scholar 

  21. V. Strassen, “Gaussian elimination is not optimal”,Numerische Mathematik 13 (1969) 354–356.

    Google Scholar 

  22. K. Steiglitz and P. Weiner, “Some improved algorithms for computer solution of the traveling salesman problem”,Proceedings 6th annual Allerton conference on circuit and system theory, (1968) pp. 814–821.

  23. S.L. Savage, P. Weiner and M.J. Krone, “Convergent local search”, Research Report 14, Yale University, Dept. of Computer Science (1973).

  24. K. Steiglitz, P. Weiner and D.J. Kleitman, “The design of minimum cost survivable networks”,IEEE Transactions on Circuit Theory CT-16 (1969) 455–460.

    Google Scholar 

  25. P. Weiner, S.L. Savage and A. Bagchi, “Neighborhood search algorithms for guaranteeing optimal traveling salesman tours must be inefficient”,Journal of Computer and Systems Sciences 12(1) (1976) 25–35.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Harvard University, Cambridge, MA, USA

    Christos H. Papadimitriou

Authors
  1. Christos H. Papadimitriou
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This Research was supported by NSF Grant GK-420488, the U.S. Army Research Office-Durham under Grant DAHC04-75-G0192, and an IBM Fellowship.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Papadimitriou, C.H. The adjacency relation on the traveling salesman polytope is NP-Complete. Mathematical Programming 14, 312–324 (1978). https://doi.org/10.1007/BF01588973

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01588973

Key words

Search

Navigation