Speaker: Michael Wigal (UIUC)
Title: Traveling Salesperson Walks in Subcubic Graphs
Abstract:
We will show that if G is a 2-connected subcubic graph on n vertices with n_2 vertices of degree 2, then G has a TSP walk of length at most (5n + 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 + n_2)/4 - 1 (respectively, 5n/4 - 2). We will outline how a quadratic-time algorithm can be obtained from the proof, thus yielding a 5/4-approximation algorithm for graphic TSP of simple cubic graphs, improving upon the prior best guarantee of 9/7.
Joint work with Youngho Yoo and Xingxing Yu.
