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. Halldórsson [SODA 1995] showed that for every δ > 0 the Independent Set problem has a polynomial-time (d - 1 2 + δ) -approximation algorithm in K 1 , d -free graphs. We extend this result by showing that K a , b -free graphs admit a polynomial-time O (α (G) 1 - 1 / a) -approximation, where α (G) is the size of a maximum independent set in G. Furthermore, we complement the result of Halldórsson by showing that for some γ = Θ (d / log d) , there is no polynomial-time γ -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 , 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 , 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 δ > 0 such that no δ -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 (k) . Finally, we consider the parameterization by the excluded graph H, and show that under the ETH, Independent Set has no n o (α (H)) algorithm in H-free graphs. Also, we prove that there is no d / k o (1) -approximation algorithm for K 1 , d -free graphs with runtime f (d , k) · n O (1) , under the deterministic Gap-ETH. [ABSTRACT FROM AUTHOR]