Parameterized Inapproximability of Independent Set in $H$-Free Graphs

Abstract

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 $\delta >0$ IS has a polynomial-time $(\frac{d-1}{2}+\delta )$-approximation in $K_{1,d}$-free graphs. We extend this result by showing that $K_{a,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 Halldórsson by showing that for some $\gamma =\Theta (d/\log d),$ there is no polynomial-time $\gamma$-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)\cdot 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)\cdot n^{O(1)}$ time. Also, under the stronger randomized Gap-ETH there is no such approximation algorithm with runtime $f(k)\cdot n^{o(\sqrt{k})}$. Finally, we consider the parameterization by the excluded graph $H$, and show that under the ETH, IS has no $n^{o(\alpha (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)}$.

Preliminary version of the paper in WG 2020 proceedings