# 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$ 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:

1. Since vertices of independent set have degree at most $k$, we first remove from $G$ all vertices whose degree is more than $k$.
2. There are now only $k^2$ edges in the current graph.
3. 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)$.
4. 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?

• The complementary problem is called vertex cover, and the parameterized vertex cover has been widely studied. You can find many results by google – Bangye Mar 13 '18 at 13:57

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.
Since complement of vertex cover is independent set, and there is $2^{O(k)}\cdot n^{O(1)}$ time algorithm for finding vertex cover of size at most $k$, it will imply $2^{O(k)}\cdot n^{O(1)}$ time algorithm for the problem considered.