In the general case finding a Maximum Independent Subset of a Graph is NP-Hard.
However consider the following subset of graphs:
- Create an $N \times N$ grid of unit square cells.
- Build a graph $G$ by creating a vertex corresponding to every cell. Notice that there are $N^2$ vertices.
- Create an edge between two vertices if their cells share a side. Notice there are $2N(N-1)$ edges.
A Maximum Independent Subset of $G$ is obviously a checker pattern. A cell at the $R$th row and $C$th column is part of it if $R+C$ is odd.
Now we create a graph $G'$ by copying $G$ and removing some vertices and edges. (If you remove a vertex also remove all edges it ended of course. Also note you can remove an edge without removing one of the vertices it ends.)
By what algorithm can we find a Maximum Independent Subset of $G'$?