Approximating TSP walks in subcubic graphs

DOI10.1016/J.JCTB.2022.09.002MaRDI QIDQ6385429arXivFDO

Authors Michael C. Wigal, Youngho Yoo, Xingxing Yu

Publication date 12 December 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.JCTB.2022.09.002

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

arXiv classification

cs.DMcs.DSmath.CO

Abstract: 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 $frac5n+n_{2}4-1$, confirming a conjecture of Dvov{r}'ak, Kr'al', and Mohar. This bound is best possible; there are infinitely many subcubic and cubic graphs whose minimum TSP walks have lengths $frac5n+n_{2}4-1$ and $frac5n4-2$ respectively. We characterize the extremal subcubic examples meeting this bound. We also give a quadratic-time combinatorial algorithm for finding such a TSP walk. In particular, we obtain a $frac54$-approximation algorithm for the graphic TSP on simple cubic graphs, improving on the previously best known approximation ratio of $frac97$.

This page was built for publication: Approximating TSP walks in subcubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6385429)