Light spanners and approximate TSP in weighted graphs with forbidden minors
Michelangelo Grigni, Papa A. Sissokho · Symposium on Discrete Algorithms · 2002
Given an edge weighted graph G with n vertices and no Kτ-minor and a small positive constant e, we show that a simple greedy algorithm [1] finds a spanning subgraph approximating all shortest-path distances within a factor of 1 + e, and with total edge weight at most O((τ√logτ · logn)/e) times the weight of a minimum spanning tree. This result implies a quasi-polynomial time approximation scheme (QPTAS) for the traveling salesman problem (TSP) in such graphs, with running time nO((τ4√logτ·log n·log log n)/e2).Our analysis shows that a graph with detour gap number [5] Ω(τ√logτ · log n) has a Kτ-minor. We also show that this dependence on n is nearly tight, by exhibiting graphs with no K6-minor (apex graphs) and detour gap number Ω((log n)/log log n).As a step towards eliminating the log n factors the first paragraph, we propose a generalized detour gap number, now depending on e, and we show that it remains bounded for apex graphs and some similar graph families.