  The size of a largest independent set of vertices in a given graph $G$ is
denoted by $\alpha(G)$ and is called its independence number (or stability
number). Given a graph $G$ and an integer $K,$ it is NP-complete to decide
whether $\alpha(G) \geq K.$ An upper bound for the independence number
$\alpha(G)$ of a given graph $G$ with $n$ vertices and $m $ edges is given by
$\alpha(G) \leq p:=\lfloor\frac{1}{2} + \sqrt{\frac{1}{4} + n^2 - n -
2m}\rfloor.$
  In this paper we will consider maximum independent sets near this upper
bound. Our main result is the following: There exists an algorithm with time
complexity $O(n^2)$ that, given as an input a graph $G$ with $n$ vertices, $m$
edges, $p:=\lfloor\frac{1}{2} + \sqrt{\frac{1}{4} + n^2 - n - 2m}\rfloor,$ and
an integer $k \geq 0$ with $p \geq 2k+1,$ returns an induced subgraph $G_{p,k}$
of $G$ with $n_0 \leq p+2k+1$ vertices such that $\alpha(G) \leq p-k$ if and
only if $\alpha(G_{p,k}) \leq p-k.$ Furthermore, we will show that we can
decide in time $O(1.2738^{3k} + kn)$ whether $\alpha(G_{p,k}) \leq p-k.$
