Czumaj, Artur2; Halldorsson, Marcús Mar3; Lingas, Andrzej4; Nilsson, Johan Peter5
1 BRICS Basic Research in Computer Science, Faculty of Science, Aarhus University, Aarhus University2 New Jersey Institute of Technology3 University of Iceland4 Lund University5 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University
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.
Information Processing Letters, 2005, Vol 94, Issue 2, p. 49-53