Summary: Given as input an edge-weighted graph, we analyze two algorithms for finding subgraphs with low total edge weight. The first algorithm finds a separator subgraph with a small number of components, and is analyzed for graphs with an arbitrary excluded minor. The second algorithm finds a spanner with small stretch factor, and is analyzed for graphs in a hereditary family \({\mathcal G}(k)\). These results imply (i) a QPTAS (Quasi-Polynomial Time Approximation Scheme) for the TSP (Traveling Salesperson Problem) in unweighted graphs with an excluded minor, and (ii) a QPTAS for the TSP in weighted graphs with bounded genus.
For the entire collection see [Zbl 0941.00034].