Parameterized Inapproximability of Independent Set in H-Free Graphs

Abstract

We study the Independent Set problem in H-free graphs, i.e., graphs excluding some fixed graph H as an induced subgraph. We prove several inapproximability results both for polynomial-time and parameterized algorithms.

Keywords

• Parameterized Inapproximability
• Independent Set
• H-Free Graphs