3
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ If $k$ is part of the input or a fixed constant then the problem is NP-hard. $\endgroup$ – Kaveh Apr 10 '13 at 19:15
  • 1
    $\begingroup$ See here for $k=1$: cs.stackexchange.com/questions/10573/… $\endgroup$ – frafl Apr 10 '13 at 19:15
7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

See Sherali and Smith's 2006 paper A polyhedral study of the generalized vertex packing problem. They consider a subset of vertices whose induced subgraph has at most $k$ edges.

There are many other generalizations of independent set and clique, based on degree, density, number of edges, distance, diameter, etc.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.