Parameterized Inapproximability of Independent Set in $H$-Free Graphs
Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai, Paweł Rzążewski · arXiv (Cornell University) · 2020
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 $(\frac{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)\cdot 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) \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(α(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)}$.