Tuesday, Dec 7, 3pm ET (8pm GMT, 9am Wed NZDT)
Michael Wigal, Georgia Tech
Approximating TSP walks in subcubic graphs

Abstract:

We will show that if $G$ is a $2$-connected simple subcubic graph on $n$ vertices with $n_2$ vertices of degree $2$, then $G$ has a TSP walk of length at most $5n/4 + n_2/4 -1$, establishing a conjecture of Dvořák, Kráľ, and Mohar. This upper bound is best possible. In particular, there are infinitely many subcubic (respectively, cubic) graphs whose minimum TSP walks have length $5n/4 + n_2/4 -1$ (respectively, $5n/4 – 2$). Our proof implies a quadratic-time algorithm for finding such a TSP walk, thereby giving a $5/4$ approximation algorithm for the graphic TSP on simple cubic graphs and improving on the previously best known approximation ratio of $9/7$.

Joint work with Youngho Yoo and Xingxing Yu.