2017/03/30 by Glencora Borradaile, Hung Le, Borradaile, Glencora +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1703.10633
openalex publication_date 2017/03/30 · openalex created_date 2017/04/14 · openalex updated_date 2026/07/28
Grigni and Hung~\citeGH12 conjectured that H-minor-free graphs have (1+ε)-spanners that are light, that is, of weight g(|H|,ε) times the weight of the minimum spanning tree for some function g. This conjecture implies the \em efficient polynomial-time approximation scheme (PTAS) of the traveling salesperson problem in H-minor free graphs; that is, a PTAS whose running time is of the form 2f(ε)nO(1) for some function f. The state of the art PTAS for TSP in H-minor-free-graphs has running time n1/εc. We take a further step toward proving this conjecture by showing that if the bounded treewidth graphs have light greedy spanners, then the conjecture is true. We also prove that the greedy spanner of a bounded pathwidth graph is light and discuss the possibility of extending our proof to bounded treewidth graphs.