Parameterized Inapproximability of Independent Set in H-Free Graphs

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. Halldorsson [SODA 1995] showed that for every delta > 0 the INDEPENDENT SET problem has a polynomial-time (d-1/2 + delta)-approximation algorithm in K-1,K-d-free graphs. We extend this result by showing that K-a,K-b-free graphs admit a polynomial-time O(alpha(G)(1-1/a))-approximation, where alpha (G) is the size of a maximum independent set in G. Furthermore, we complement the result of Halldorsson by showing that for some gamma = Theta (d / log d), there is no polynomial-time gamma-approximation algorithm for these graphs, unless NP = ZPP. Bonnet et al. [Algorithmica 2020] showed that INDEPENDENT SET parameterized by the size k of the independent set is W[1]-hard on graphs which do not contain (1) a cycle of constant length at least 4, (2) the star K-1,K-4, and (3) any tree with two vertices of degree at least 3 at constant distance. We strengthen this result by proving three inapproximability results under different complexity assumptions for almost the same class of graphs (we weaken conditions (1) and (2) that G does not contain a cycle of constant length at least 5 or K-1,K-5). First, under the ETH, there is no f (k) . n(o(k/ log k)) algorithm for any computable function f. Then, under the deterministic Gap-ETH, there is a constant delta > 0 such that no delta-approximation can be computed in f (k) . n(O(1)) time. Also, under the stronger randomized Gap-ETH there is no such approximation algorithm with runtime f (k) . n(o(root k)). Finally, we consider the parameterization by the excluded graph H, and show that under the ETH, INDEPENDENT SET has no n(o(alpha(H))) algorithm in H-free graphs. Also, we prove that there is no d/k(o(1)) -approximation algorithm for K-1,K-d-free graphs with runtime f (d, k) . n(O(1)), under the deterministic Gap-ETH.