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.
Bibliographical noteFunding Information:
* Corresponding author. E-mail addresses: email@example.com (A. Czumaj), firstname.lastname@example.org (M.M. Halldórsson), email@example.com (A. Lingas), firstname.lastname@example.org (J. Nilsson). 1 Research supported in part by NSF grants CCR-0105701 and CCR-0313219. 2 BRICS (Basic Research in Computer Science) is funded by the Danish National Research Foundation.
- Approximation algorithms
- Bounded treewidth
- NP-hard problems
- Partial k-trees