Local Tree-Width, Excluded Minors, and Approximation Algorithms
The local tree-width of a graphG = (V, E) is the function ltw : N → N that associates with every∈ N the maximal tree-width of an r-neighborhood in G. Our main graph theoretic result is a decomposition theorem for graphs with excluded minors that essentially says that such graphs can b e decomposed into trees of graphs of bounded local tree-width. As an application of this theorem, we show that a number of com binatorial optimization problems, such as M INIMUM VERTEX COVER, M INIMUM DOMINATING SET, and MAXIMUM INDEPENDENTSET have a polynomial time approximation scheme when restricted to a class of graphs with an excluded minor.