TSP Tours in Cubic Graphs: Beyond 4/3

Abstract

After a sequence of improvements Boyd et al. [TSP on cubic and subcubic graphs, Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 6655, Springer, Heidelberg, 2011, pp. 65--77] proved that any 2-connected graph whose $n$ vertices have degree 3, i.e., a cubic 2-connected graph, has a Hamiltonian tour of length at most (4/3)n, establishing in particular that the integrality gap of the subtour LP is at most 4/3 for cubic 2-connected graphs and matching the conjectured value of the famous 4/3 conjecture. In this paper we improve upon this result by designing an algorithm that finds a tour of length (4/3-1/61236)n, implying that cubic 2-connected graphs are among the few interesting classes of graphs for which the integrality gap of the subtour LP is strictly less than 4/3. With the previous result, and by considering an even smaller $\epsilon$, we show that the integrality gap of the TSP relaxation is at most $4/3- \epsilon$ even if the graph is not 2-connected (i.e., for cubic connected graphs), implying that the approximability threshold of the TSP in cubic graphs is strictly below 4/3. Finally, using similar techniques we show, as an additional result, that every Barnette graph admits a tour of length at most (4/3 - 1/18)n.