  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 Erd\H{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 Erd\H{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.
