A PTAS for subset TSP in minor-free graphs

Abstract

We give the first PTAS for the subset Traveling Salesperson Problem (TSP) in $H$-minor-free graphs. This resolves a long standing open problem in a long line of work on designing PTASes for TSP in minor-closed families initiated by Grigni, Koutsoupias and Papadimitriou in FOCS'95. The main technical ingredient in our PTAS is a construction of a nearly light subset $(1+\epsilon )$-spanner for any given edge-weighted $H$-minor-free graph. This construction is based on a necessary and sufficient condition given by \emph{sparse spanner oracles}: light subset spanners exist if and only if sparse spanner oracles exist. This relationship allows us to obtain two new results: _ An $(1+\epsilon )$-spanner with lightness $O({\epsilon }^{-d+2})$ for any doubling metric of constant dimension $d$. This improves the earlier lightness bound ${\epsilon }^{-O(d)}$ obtained by Borradaile, Le and Wulff-Nilsen. _ An $(1+\epsilon )$-spanner with sublinear lightness for any metric of constant correlation dimension. Previously, no spanner with non-trivial lightness was known.

43 pages, 7 figures, complete revision of the old version, with new results

References in corpus (3)

• On Pairwise Spanners
• A light metric spanner
• Truly Optimal Euclidean Spanners