2017/11/02 by Borradaile, Glencora, Le, Hung, Wulff-Nilsen, Christian
#68W25 #68W40 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1711.00821
We show that every H-minor-free graph has a light (1+ε)-spanner, resolving an open problem of Grigni and Sissokho and proving a conjecture of Grigni and Hung. Our lightness bound is O((σH)/(ε3)log \frac1ε) where σH = |V(H)|√(log |V(H)|) is the sparsity coefficient of H-minor-free graphs. That is, it has a practical dependency on the size of the minor H. Our result also implies that the polynomial time approximation scheme (PTAS) for the Travelling Salesperson Problem (TSP) in H-minor-free graphs by Demaine, Hajiaghayi and Kawarabayashi is an efficient PTAS whose running time is 2^OH((1)/(ε4)log \frac1ε)nO(1) where OH ignores dependencies on the size of H. Our techniques significantly deviate from existing lines of research on spanners for H-minor-free graphs, but build upon the work of Chechik and Wulff-Nilsen for spanners of general graphs.