<p>See Sherali and Smith's 2006 paper <em><a href="http://link.springer.com/article/10.1007/s10107-004-0504-0" rel="nofollow">A polyhedral study of the generalized vertex packing problem</a></em>. They consider a subset of vertices whose induced subgraph has at most $k$ edges.</p>

<p>There are many <a href="http://www.sciencedirect.com/science/article/pii/S0377221712007679" rel="nofollow">other generalizations of independent set and clique</a>, based on <a href="http://link.springer.com/article/10.1007/s11590-009-0146-5" rel="nofollow">degree</a>, <a href="http://www.sciencedirect.com/science/article/pii/S0166218X12002843" rel="nofollow">density</a>, number of edges, distance, <a href="http://www.sciencedirect.com/science/article/pii/S1572528612000163" rel="nofollow">diameter</a>, etc. </p>

<p>Independent sets go by other names (e.g., vertex packing, stable set, anticlique), so you might search for them as well.</p>

CC BY-SA 3.0
2013-04-12T03:48:18.510Z
2013-04-12T03:48:18.510Z
Austin Buchanan
<p>Not exactly what you're looking for, but Dinur and Safra, in their <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.125.334&amp;rep=rep1&amp;type=pdf">celebrated paper on the hardness of vertex cover</a>, 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).</p>

<p>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.</p>

<p>Problem: Distinguish between the following two cases:</p>

<ul>
<li>YES case: $G$ has an independent set of size $m$.</li>
<li>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).</li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2013-04-10T21:14:04.553Z
2013-04-10T21:14:04.553Z
Yuval Filmus
<p>I know the definition of the independent set problem in graph theory.  An independent set cannot contain any two adjacent vertices.</p>

<p>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?</p>

CC BY-SA 3.0
2013-04-10T19:15:44.487Z
If $k$ is part of the input or a fixed constant then the problem is NP-hard.
Kaveh
CC BY-SA 3.0
2013-04-10T19:15:52.593Z
See here for $k=1$: http://cs.stackexchange.com/questions/10573/prove-finding-a-near-clique-is-np-complete
frafl
<ds.algorithms><graph-theory><co.combinatorics><linear-programming><independence>
Generalization of independent set
Paul Reiners
# Generalization of independent set

(Asked by: username_0 on 2013-04-10)

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?

**Tags:** ds.algorithms, graph-theory, co.combinatorics, linear-programming, independence
> **Comments:**
> **username_1**: If $k$ is part of the input or a fixed constant then the problem is NP-hard.  
> **username_2**: See here for $k=1$: http://cs.stackexchange.com/questions/10573/prove-finding-a-near-clique-is-np-complete  

---

## 2 answers

### Answer by username_4 on 2013-04-10. Score: 7 | Accepted answer

Not exactly what you're looking for, but Dinur and Safra, in their [celebrated paper on the hardness of vertex cover](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.125.334&rep=rep1&type=pdf), prove that the following promise problem is NP-hard for every fixed $r,\epsilon > 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.


---

### Answer by username_3 on 2013-04-12. Score: 3

See Sherali and Smith's 2006 paper *[A polyhedral study of the generalized vertex packing problem](http://link.springer.com/article/10.1007/s10107-004-0504-0)*. They consider a subset of vertices whose induced subgraph has at most $k$ edges.

There are many [other generalizations of independent set and clique](http://www.sciencedirect.com/science/article/pii/S0377221712007679), based on [degree](http://link.springer.com/article/10.1007/s11590-009-0146-5), [density](http://www.sciencedirect.com/science/article/pii/S0166218X12002843), number of edges, distance, [diameter](http://www.sciencedirect.com/science/article/pii/S1572528612000163), etc.

Independent sets go by other names (e.g., vertex packing, stable set, anticlique), so you might search for them as well.


---

