Parameterized Inapproximability of Independent Set in H-Free Graphs

W pracy badamy złożoność problemu znajdowania największego zbioru niezależnego w grafach, które nie zawierają ustalonego grafu H jako podgrafu indukowanego. Pokazujemy, że przy pewnych założeniach na graf H, problem nie da się dobrze aproksymować nawet w czasie f(k) * poly(n), gdzie k jest rozmiarem szukanego rozwiązania, a f dowolną funkcją.

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.