Parameterized Inapproximability of Independent Set in H-Free Graphs

Abstrakt

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.

Klíčová slova

• Parameterized Inapproximability
• Independent Set
• H-Free Graphs