Generalization of independent set I know the definition of the independent set problem in graph theory.  An independent set cannot contain any two adjacent vertices.

How about if you allow no more than $k$ pairs of adjacent vertices?  Does this more general problem have a name?  Are there techniques for solving it?  In particular, are there any techniques for solving it with linear programming?
Not exactly what you're looking for, but Dinur and Safra, in their celebrated paper on the hardness of vertex cover, prove that the following promise problem is NP-hard for every fixed $r,\epsilon &gt; 0$ (using the PCP theorem and Raz's parallel repetition theorem).

Instance: A graph $G$ whose vertex set is composed of $m$ sets $V_1,\ldots,V_m$ of size $r$, each of them forming an $r$-clique.

Problem: Distinguish between the following two cases:


YES case: $G$ has an independent set of size $m$.
NO case: Every set $A \subseteq V$ containing more than $\epsilon m$ vertices contains a clique of size $h = \lfloor \epsilon r^{1/c} \rfloor$ (where $c$ is some universal constant).


More explicitly, for any NP language $L$ there is a polytime $f$ mapping instances of $L$ to instances of this promise problem, in such a way that if $x \in L$ then $f(x)$ is a YES instance, and if $x \notin L$ then $f(x)$ is a NO instance.