Local Tree-Width,Excluded Minors,and Approximation Algorithms

The local tree-width ofa graph G=(V,E) is the functionltw^G : that associateswith every r the maximaltree-width of an r-neighborhood inG. Our main grapht heoreticresult is a decomposition theorem for graphs with excludedminors, which says that such graphs can be decomposed into treesof graphs of almost bounded local tree-width.As an application of this theorem, we show that a numberof combinatorial optimization problems, suchasMinimum Vertex Cover,Minimum Dominating Set,and Maximum IndependentSet have a polynomial time approximation scheme whenrestricted to a class of graphs with an excluded minor.