A PTAS for subset TSP in minor-free graphs

We give the first PTAS for the subset Traveling Salesperson Problem (TSP) in H-minorfree 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 + )-spanner for any given edge-weighted H-minor-free graph. This construction is based on a necessary and sufficient condition given by 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 + )-spanner with lightness O( -d+2 ) for any doubling metric of constant dimension d. This improves the earlier lightness bound -O(d) obtained by Borradaile, .

• An (1+ )-spanner with sublinear lightness for any metric of constant correlation dimension. Previously, no spanner with non-trivial lightness was known.

• A major part of this work was done while the author was a graduate student at Oregon State University.

1 A polynomial-time approximation scheme is an algorithm which, for a given fixed error parameter , finds a solution whose value is within 1 ± of the optimal solution in polynomial time.