Parameterized Inapproximability of Independent Set in H-Free Graphs
share
We study the Independent Set (IS) 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 IS has a polynomial-time (d-1/2+δ)-approximation 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 for these graphs, unless NP = ZPP. Bonnet et al. [IPEC 2018] showed that IS 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 condition (2) that G does not contain 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, IS has no n^o(α(H)) algorithm in H-free graphs and under Gap-ETH there is no d/k^o(1)-approximation for K_1,d-free graphs with runtime f(d,k) n^O(1).
READ FULL TEXT