Abstract
We study the Travelling 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 values of the TSP and its linear programming relaxation, is 4/3. Using polyhedral techniques in an interesting way, we obtain a polynomial-time 4/3-approximation algorithm for this problem on cubic graphs, improving upon Christofides’ 3/2-approximation, and upon the 3/2 − 5/389 ≈ 1.487-approximation ratio by Gamarnik, Lewenstein and Svirdenko for the case the graphs are also 3-edge connected. We also prove that, as an upper bound, the 4/3 conjecture is true for this problem on cubic graphs. For subcubic graphs we obtain a polynomial-time 7/5-approximation algorithm and a 7/5 bound on the integrality gap.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, N., Garg, N., Gupta, S.: A 4/3-approximation for TSP on cubic 3-edge-connected graphs (2011) (manuscript)
Akiyama, T., Nishizeki, T., Saito, N.: NP-completeness of the hamiltonian cycle problem for bipartite graphs. Journal of Information Processing 3, 73–76 (1980)
Arora, S., Grigni, M., Karger, D., Klein, P., Woloszyn, A.: A polynomial-time approximation scheme for weighted planar graph TSP. In: Proc. of the 9th ACM–SIAM Symposium on Discrete Algorithms, pp. 33–41 (1998)
Barahona, F.: Fractional packing of T-joins. SIAM Journal on Discrete Math. 17, 661–669 (2004)
Benoit, G., Boyd, S.: Finding the exact integrality gap for small travelling salesman problems. Math. of Operations Research 33, 921–931 (2008)
Berman, P., Karpinski, M.: 8/7-approximation algorithm for 1,2-TSP. In: Proc. 17th ACM SIAM Symposium on Discrete Algorithms, pp. 641–648 (2006)
Boyd, S., Iwata, S., Takazawa, K.: Finding 2-Factors Covering 3- and 4-Edge Cuts in Bridgeless Cubic Graphs Kyoto University (2010) (manuscript)
Csaba, B., Karpinski, M., Krysta, P.: Approximability of dense and sparse instances of minimum 2-connectivity, tsp and path problems. In: Proc. 13th ACM–SIAM Symposium on Discrete Algorithms, pp. 74–83 (2002)
Christofides, N.: Worst case analysis of a new heuristic for the traveling salesman problem, Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh (1976)
Cornuéjols, G., Fonlupt, J., Naddef, D.: The traveling salesman on a graph and some related integer polyhedra. Math. Programming 33, 1–27 (1985)
Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. of Res. National Bureau of Standards B 69, 125–130 (1965)
Fotakis, D., Spirakis, P.: Graph properties that facilitate travelling. Electronic Colloquium on Computational Complexity 31, 1–18 (1998)
Fulkerson, D.: Blocking and anti-blocking pairs of polyhedra. Math Programming 1, 168–194 (1971)
Gamarnik, D., Lewenstein, M., Sviridenko, M.: An improved upper bound for the TSP in cubic 3-edge-connected graphs. OR Letters 33, 467–474 (2005)
Garey, M., Johnson, D., Tarjan, R.: The planar hamiltonian circuit problem is NP-complete. SIAM Journal of Computing 5, 704–714 (1976)
Gharan, S.O., Saberi, A., Singh, M.: A Randomized Rounding Approach to the Traveling Salesman Problem (2011) (manuscript)
Grigni, M., Koutsoupias, E., Papadimitriou, C.: An approximation scheme for planar graph TSP. In: Proc. 36th Annual Symposium on Foundations of Computer Science, pp. 640–645 (1995)
Hartvigsen, D., Li, Y.: Maximum cardinality simple 2-matchings in subcubic graphs, University of Notre Dame (2009) (manuscript)
Kaiser, T., Král’, D., Norine, S.: Unions of perfect matchings in cubic graphs. Electronic Notes in Discrete Math. 22, 341–345 (2005)
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem–A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)
Naddef, D., Pulleyblank, W.: Matchings in regular graphs. Discrete Math. 34, 283–291 (1981)
Papadimitriou, C., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18, 1–11 (1993)
Petersen, J.: Die Theorie der regulären graphen. Acta Math. 15, 193–220 (1891)
Shmoys, D., Williamson, D.: Analyzing the Held-Karp TSP bound: A monotonicity property with application. Information Processing Letters 35, 281–285 (1990)
Wolsey, L.: Heuristic analysis, linear programming and branch and bound. Math. Programming Study 13, 121–134 (1980)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boyd, S., Sitters, R., van der Ster, S., Stougie, L. (2011). TSP on Cubic and Subcubic Graphs. In: Günlük, O., Woeginger, G.J. (eds) Integer Programming and Combinatoral Optimization. IPCO 2011. Lecture Notes in Computer Science, vol 6655. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20807-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-20807-2_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20806-5
Online ISBN: 978-3-642-20807-2
eBook Packages: Computer ScienceComputer Science (R0)