Prove that finding largest subset of undirected graph that is almost independent is NP-hard A subset $S$ of vertices in an undirected graph $G$ is called almost independent if at most 100 edges in $G$ have both endpoints in $S$. Prove that finding the size of the largest almost-independent set of vertices in a given undirected graph is NP-hard.


For these types of problems, I know that I should try to find a polynomial time reduction of an algorithm that is already known to be NP-hard.  I tried my hand at trying to manipulate the k-coloring problem, but without any luck. 

How would I go about proving this function is NP-hard?
The proof is by reduction from independent set. Given an instance $(G,k)$ of independent set, construct a new instance $(G',1000k)$ in the following way: each vertex $x \in G$ is replaced by an independent set $I_x$ of size 1000, and each edge $(x,y)$ is replaced by a complete bipartite graph $I_x \times I_y$.

If $G$ contains an independent set $S$ of size $k$, then $G'$ contains an independent set $\bigcup_{x \in S} I_x$ of size $1000k$. In the other direction, suppose that $G'$ contains an almost independent set $S$ of size $1000k$. Remove all vertices incident to any edges within $S$ to obtain an independent set $S' \subseteq S$ of size at least $1000k-200$. Let $T = \{ x : I_x \cap S' \neq \emptyset \}$, and note that $T$ is an independent set of $G$. Finally, since $S'$ can contain at most 1000 vertices from each $I_x$, we see that $|T| \geq \lceil |S'|/1000 \rceil = k$.