Polynomial-time Approximation of Independent Set Parameterized by Treewidth

Parinya Chalermsook, Fedor Fomin, Thekla Hamm +3

We prove the following result about approximating the maximum independent set in a graph. Informally, we show that any approximation algorithm with a ``non-trivial'' approximation…