We study the approximability of the Maximum Independent Set (MIS) problem in $H$-free graphs (that is, graphs which do not admit $H$ as an induced subgraph). As one motivation we investigate the following conjecture: for every fixed graph $H$, there exists a constant $delta > 0$ such that MIS can be $n^{1 - delta}$-approximated in $H$-free graphs, where $n$ denotes the number of vertices of the input graph. We first prove that a constructive version of the celebrated ErdH{o}s-Hajnal conjecture implies ours. We then prove that the set of graphs $H$ satisfying our conjecture is closed under the so-called graph substitution. This, together with the known polynomial-time algorithms for MIS in $H$-free graphs (e.g. $P_6$-free and fork-free graphs), implies that our conjecture holds for many graphs $H$ for which the ErdH{o}s-Hajnal conjecture is still open. We then focus on improving the constant $delta$ for some graph classes: we prove that the classical Local Search algorithm provides an $OPT^{1-frac{1}{t}}$-approximation in $K_{t,t}$-free graphs (hence a $sqrt{OPT}$-approximation in $C_4$-free graphs), and, while there is a simple $sqrt{n}$-approximation in triangle-free graphs, it cannot be improved to $n^{frac{1}{4}-varepsilon}$ for any $varepsilon > 0$ unless $NP subseteq BPP$. More generally, we show that there is a constant $c$ such that MIS in graphs of girth $gamma$ cannot be $n^{frac{c}{gamma}}$-approximated. Up to a constant factor in the exponent, this matches the ratio of a known approximation algorithm by Monien and Speckenmeyer, and by Murphy. To the best of our knowledge, this is the first strong (i.e., $Omega(n^delta)$ for some $delta > 0$) inapproximability result for Maximum Independent Set in a proper hereditary class.
Download