An Improved Upper Bound for the TSP in 3-Connected Cubic Graphs

We consider the classical minimum Travelling Salesman Problem on the class of 3-edge-connected cubic graphs. More specifically we consider their (shortest path) metric completions. The well-known conjecture states that the subtour elimination LP relaxation on the min TSP yields a 4/3 approximation factor, yet the best known ap-proximation factor is 3/2. The 3-edge-connected cubic graphs have the special property of being ”LP-oblivious” to the subtour elimination LP relaxation and hence provide a class that potentially would show a tight 3/2 bound. However, we show that on this class of graphs one can achieve an approximation factor better than the general 3/2.