Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth

We present a generic scheme for approximating NP-hard problems on graphs of treewidth k=ω(logn). When a tree-decomposition of width ℓ is given, the scheme typically yields an ℓ/logn-approximation factor; otherwise, an extra logk factor is incurred. Our method applies to several basic subgraph and partitioning problems, including the maximum independent set problem.