A PTAS for subset TSP in minor-free graphs

04/04/2018

∙

by   Hung Le, et al.

∙

0

∙

share

We give the first polynomial time approximation scheme for the subset Traveling Salesperson Problem (subset TSP) in H-minor-free graphs. Our main technical contribution is a polynomial time algorithm that, given an edge-weighted H-minor-free graph G and a set of k terminals T, finds a subgraph of G with weight at most O_H(poly(1/ϵ) k) times the weight of the minimum Steiner tree for T that preserves pairwise distances between terminals up to (1+ϵ) factor. This is the first such spanner for H-minor-free graphs. Given this spanner, we use the contraction decomposition of Demaine, Hajiaghayi and Kawarabayashi to obtain a PTAS for the subset TSP problem. Our PTAS generalizes PTASes for the same problem by Klein for planar graphs and by Borradaile, Demaine and Tazari for bounded genus graphs.