Youngho Yoo (유영호), Approximating TSP walks in subcubic graphs

The Graphic Travelling Salesman Problem is the problem of finding a spanning closed walk (a TSP walk) of minimum length in a given connected graph. The special case of the Graphic TSP on subcubic graphs has been studied extensively due to their worst-case behaviour in the famous $\frac{4}{3}$-integrality-gap conjecture on the “subtour elimination” linear programming relaxation of the Metric TSP.

We prove that every simple 2-connected subcubic graph on $n$ vertices with $n_2$ vertices of degree 2 has a TSP walk of length at most $\frac{5n+n_2}{4}-1$, confirming a conjecture of Dvořák, Král’, and Mohar. This bound is best possible and we characterize the extremal subcubic examples meeting this bound. We also give a quadratic time combinatorial algorithm to find such a TSP walk. In particular, we obtain a $\frac{5}{4}$-approximation algorithm for the Graphic TSP on cubic graphs. Joint work with Michael Wigal and Xingxing Yu.