Skip to main content
SpringerLink
Log in

The traveling salesman problem on cubic and subcubic graphs

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We study the traveling salesman problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem is of interest because of its relation to the famous 4/3-conjecture for metric TSP, which says that the integrality gap, i.e., the worst case ratio between the optimal value of a TSP instance and that of its linear programming relaxation (the subtour elimination relaxation), is 4/3. We present the first algorithm for cubic graphs with approximation ratio 4/3. The proof uses polyhedral techniques in a surprising way, which is of independent interest. In fact we prove constructively that for any cubic graph on \(n\) vertices a tour of length \(4n/3-2\) exists, which also implies the 4/3-conjecture, as an upper bound, for this class of graph-TSP. Recently, Mömke and Svensson presented an algorithm that gives a 1.461-approximation for graph-TSP on general graphs and as a side result a 4/3-approximation algorithm for this problem on subcubic graphs, also settling the 4/3-conjecture for this class of graph-TSP. The algorithm by Mömke and Svensson is initially randomized but the authors remark that derandomization is trivial. We will present a different way to derandomize their algorithm which leads to a faster running time. All of the latter also works for multigraphs.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. To see that \(n\) is a lower bound for SER, sum all of the so-called “degree constraints” for SER. Dividing the result by 2 shows that the sum of the edge variables in any feasible SER solution equals \(n\).

  2. Note that a bound of \(n/6+1\) cycles is sufficient for the the 4/3-approximation and it follows from results in [27] (see Sect. 3) that such a cycle cover indeed always exists.

References

  1. Aggarwal, N., Garg, N., Gupta, S.: A 4/3-approximation for TSP on cubic 3-edge-connected graphs. Tech. Rep. (2011). http://arxiv.org/abs/1101.5586

  2. Akiyama, T., Nishizeki, T., Saito, N.: NP-completeness of the Hamiltonian cycle problem for bipartite graphs. J. Inf. Process. 3, 73–76 (1980)

    MATH  MathSciNet  Google Scholar 

  3. Arora, S., Grigni, M., Karger, D., Klein, P., Woloszyn, A.: A polynomial-time approximation scheme for weighted planar graph TSP. In: Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, pp. 33–41 (1998)

  4. Barahona, F.: Fractional packing of t-joins. SIAM J. Discret. Math. 17, 661–669 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  5. Benoit, G., Boyd, S.: Finding the exact integrality gap for small travelling salesman problems. Math. Oper. Res. 33, 921–931 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  6. Bérczi, K., Végh, L.A.: Restricted \(b\)-matchings in degree-bounded graphs. In: Proceedings of the 14th Conference on Integer Programming and Combinatorial, Optimization, pp. 43–56 (2010)

  7. Berman, P., Karpinski, M.: 8/7-approximation algorithm for 1,2-TSP. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 641–648 (2006)

  8. Boyd, S., Iwata, S., Takazawa, K.: Finding 2-Factors Covering 3- and 4-Edge Cuts in Bridgeless Cubic Graphs. Manuscript, Kyoto University (2010)

  9. Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: TSP on Cubic and Subcubic Graphs. Manuscript (2011). http://personal.vu.nl/r.a.sitters/papers/GraphTsp.pdf

  10. Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: TSP on cubic and subcubic graphs. Tech. Rep. arXiv (2011). http://arxiv.org/abs/1107.1052v1

  11. Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: TSP on cubic and subcubic graphs. In: Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 6655, pp. 65–77 (2011)

  12. Christofides, N.: Worst case analysis of a new heuristic for the traveling salesman problem. Tech. Rep. Report 388. Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh (1976)

  13. Correa, J.R., Larré, O., Soto, J.A.: TSP Tours in Cubic Graphs: beyond 4/3. In: Proceedings of the 20th European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 7501, pp. 790–801 (2011)

  14. Csaba, B., Karpinski, M., Krysta, P.: Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 74–83 (2002)

  15. Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bureau Stand. B 69, 125–130 (1965)

    Article  MATH  MathSciNet  Google Scholar 

  16. Fotakis, D., Spirakis, P.: Graph properties that facilitate travelling. Electron. Colloquium Comput. Complex. 5(31) (1998)

  17. Gabow, H.N.: Data structures for weighted matchings and nearest common ancestors with linking. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 434–443 (1990)

  18. Gamarnik, D., Lewenstein, M., Sviridenko, M.: An improved upper bound for the TSP in cubic 3-edge-connected graphs. OR Lett. 33, 467–474 (2005)

    Google Scholar 

  19. Garey, M., Johnson, D., Tarjan, R.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 704–714 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  20. Goemans, M.X.: Worst-case comparison of valid inequalities for the TSP. Math. Program. 69, 335–349 (1995)

    MATH  MathSciNet  Google Scholar 

  21. Grigni, M., Koutsoupias, E., Papadimitriou, C.: An approximation scheme for planar graph TSP. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pp. 640–645 (1995)

  22. Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)

    Book  MATH  Google Scholar 

  23. Hartvigsen, D., Li, Y.: Maximum cardinality simple 2-matchings in subcubic graphs. SIAM J. Optim. 21(3), 1027–1045 (2011)

    Google Scholar 

  24. Kaiser, T., Král, D., Norine, S.: Unions of perfect matchings in cubic graphs. Electron. Notes Discret. Math. 22, 341–345 (2005)

    Article  Google Scholar 

  25. Lawler, E., Lenstra, J., Kan, A.R., Shmoys, D.: The Traveling Salesman Problem-A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)

    MATH  Google Scholar 

  26. Mömke, T., Svensson, O.: Approximating graphic TSP by matchings. Tech. Report arxiv (2011)

  27. Mömke, T., Svensson, O.: Approximating graphic TSP by matchings. In: Proceedings of the 52nd Symposium Foundations of Computer Science, pp. 560–569 (2011)

  28. Mucha, M.: A 13/9 -approximation for Graphic TSP. In: Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, pp. 30–41 (2012)

  29. Naddef, D., Pulleyblank, W.: Matchings in regular graphs. Discret. Math. 34, 283–291 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  30. Oveis Gharan, S., Saberi, A., Singh, M.: A randomized rounding approach to the traveling salesman problem. In: Proceedings of the 52nd Symposium Foundations of Computer Science, pp. 550–559 (2011)

  31. Papadimitriou, C., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1–11 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  32. Petersen, J.: Die theorie der regulären graphen. Acta Math. 15, 193–220 (1891)

    Article  MATH  MathSciNet  Google Scholar 

  33. Sebö, A., Vygen, J.: Shorter tours by Nicer Ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Tech. Rep. (2012). http://arxiv.org/abs/1201.1870

  34. Shmoys, D., Williamson, D.: Analyzing the Held-Karp TSP bound: a monotonicity property with application. Inf. Process. Lett. 35, 281–285 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  35. Wolsey, L.: Heuristic analysis, linear programming and branch and bound. Math. Program. Study 13, 121–134 (1980)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada

    Sylvia Boyd

  2. Department of Operations Research, VU University Amsterdam, Amsterdam, The Netherlands

    René Sitters, Suzanne van der Ster & Leen Stougie

  3. CWI, Amsterdam, The Netherlands

    René Sitters & Leen Stougie

Authors
  1. Sylvia Boyd
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. René Sitters
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Suzanne van der Ster
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Leen Stougie
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to René Sitters.

Additional information

This research was partially supported by Tinbergen Institute, the Netherlands and the Natural Sciences and Engineering Research Council of Canada.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Boyd, S., Sitters, R., van der Ster, S. et al. The traveling salesman problem on cubic and subcubic graphs. Math. Program. 144, 227–245 (2014). https://doi.org/10.1007/s10107-012-0620-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-012-0620-1

Keywords

Mathematics Subject Classification

Search

Navigation