Minimum number of vertices whose removal makes the graph an independent set It is known that finding an independent set (or a clique) of size at least $k$ in a graph is $W[1]$ hard, so it is unlikely that there is $f(k)\cdot n^{O(1)}$ time algorithm for finding an independent set of size greater than equal to $k$.

I was looking at the complementary problem - "Whether or not removal of at most $k$ vertices from a graph can make the resulting graph an independent set".


  If the input graph $G$ contains a set $W$ of size at most $k$ for
  which $V(G)\setminus W$ is independent set, then it can be found in
  $2^{O(k \log k)}\cdot n^{O(1)}$ time as follows:
  
  
  Since vertices of independent set have degree at most $k$, we first remove from $G$ all vertices whose degree is more than $k$.
  There are now only $k^2$ edges in the current graph.
  Let $A$ be set of all vertices on which at least one edge is incident, then $V(G)\setminus A$ is an independent set of size at
  least $(n-2k^2)$.
  So $W$ must be contained in set $A$ whose size is at most $2k^2$. We can scan over all ${2k^2}\choose{k}$ subsets of A to check removal
  of which set makes the graph an independent set.
  


My question is does the new problem has $2^{O(k)}\cdot n^{O(1)}$ time algorithm?
Yes, and the algorithm is straight forward branching.

Suppose that you are given a graph $G$ and an integer $k$.  If $k = 0$, we simply return whether $G$ is an independent set.  If $G$ is an independent set, we return "yes".  Otherwise, we branch.  If there is an edge $uv$ in $G$, we recurse on $G-u, k-1$ and $G-v, k-1$.  Since the budget drops with one for every recursive call, we call ourselves at most $2^k$ times.

The correctness is left as an exercise.