Siguiente: Problemas de asignación de Un nivel arriba: Algunos problemas principales completos-NP Anterior: Partición

Problemas en gráficas

Una gráfica es un sistema G=(V,A) donde

• $V=\{v_1,\ldots,v_n\}$ es un conjunto de vértices o nodos, y
• $A\subset V^{(2)}=\{a\subset V\vert\mbox{\rm card}(a)=2\}$ es un conjunto de aristas (sin dirección).

Una gráfica se dice ser

• un clan o completa si contiene todas las ${n\choose 2}=\frac{n(n-1)}{2}$ aristas posibles, y en tal caso se le denota como K_n,
• vacía o independiente si su conjunto de aristas es vacío, y en tal caso la denotaremos por I_n.

El complemento, o gráfica complementaria, de una gráfica G=(V,A) es G^c=(V,V⁽²⁾-A), es decir

$$\forall v_1\not= v_2:\{v_1,v_2\}\mbox{\rm arista en }G^c\ \Leftrightarrow\ \{v_1,v_2\}\mbox{\rm NO es arista en }G.$$

Así, por ejemplo, K_n e I_n son gráficas complementarias una de otra. Recordamos también los conceptos siguientes:

• un recubrimiento por vértices es un subconjunto $U\subset V$ de vértices tal que toda arista tiene al menos un extremo en él, es decir, tal que
  
  $$\forall a\in A:\ a\cap U\not=\emptyset.$$
  
  

• un recubrimiento por aristas es un subconjunto $B\subset A$ de aristas tal que todo vértice está en al menos una de tales aristas, es decir, tal que
  
  $$\forall v\in V\exists a\in B: v\in a.$$
  
  

Consideremos los siguientes problemas: Recubrimiento por vértices (VC): Este problema (vertex cover) se describe como sigue:


Instancia:

Solución:




Clan (CLIQUE):


Instancia:

Solución:




Conjunto independiente:


Instancia:

Solución:




Los tres problemas anteriores se reducen entre sí debido al evidente Lema: Para una gráfica G=(V,A) y un subconjunto $U\subset V$ las siguientes tres condiciones son equivalentes a pares:

1.

U es un recibrimiento por vértices de G.

2.

V-U es un conjunto independiente en G.

3.

V-U es un clan en la gráfica complementaria G^c.

Proposición: VC es completo-NP. Demostración: VC es naturalmente un problema en la clase NP. Para ver que es difícil-NP reduciremos 3SAT a VC. Dados

• $\mbox{\bf X}=\{X_1,\ldots,X_n\}$: conjunto de n variables proposicionales,
• $\mbox{\bf C}=\{c_1,\ldots,c_m\}$: conjunto de m cláusulas de 3 literales sobre $\mbox{\bf X}$,

construiremos una instancia de VC de manera que ésta dé una instancia con respuesta positiva en VC si y sólo si la forma conjuntiva $\mbox{\bf C}$ es satisfactible. En tal caso, un recubrimiento por vértices de la instancia construída ha de determinar una asignación de valores de verdad a las variables en $\mbox{\bf X}$ que satisfaga a $\mbox{\bf C}$. Definamos

• para cada variable $X_j\in\mbox{\bf X}$, una gráfica consistente de una sola arista,
  
  $$G^j=(\{x_j,\bar{x}_j\},\{a_j=\{x_j,\bar{x}_j\}\}),$$
  
  

• para cada cláusula $c_i\in C$, una gráfica consistente de un triángulo,
  
  $$G_i=(\{u_i,v_i,w_i\},\left\{\{u_i,v_i\},\{v_i,w_i\},\{w_i,u_i\}\right\}),$$
  
  
  y
• para cada cláusula, que consta de tres literales,
  
  $$c_i=\{x_{j_{i1}}^{\epsilon_{j_{i1}}},x_{j_{i2}}^{\epsilon_{j_{i2}}},x_{j_{i3}}^{\epsilon_{j_{i3}}}\}$$
  
  
  tendemos las aristas de los vértices de G_i a los correspondientes vértices ``literales'' de las gráficas de la forma G^j siguientes
  
  $$\begin{array}{ccccc} \left\{u_i,x_{j_{i1}}^{\epsilon_{j_{i1}... ...\left\{w_i,x_{j_{i3}}^{\epsilon_{j_{i3}}}\right\} \end{array}$$
  
  
  Así pues, la gráfica construída G=(V,A) consta de 2n+3m vértices y n+6m aristas.
• Finalmente, hagamos N=n+2m.

Una solución de 3SAT da una solución de VC: Supongamos que $\mbox{\boldmath$\epsilon$ }$ es una asignación que satisface a C. Construyamos el recubrimiento U siguiente:

• Para cada $j\leq n$,
  
  $$\begin{eqnarray*}\epsilon_j=0 &\Rightarrow& \mbox{\rm poner $\bar{x}_j$\space de... ...ghtarrow& \mbox{\rm poner $x_j$\space de $G^j$\space en $U$ }. \end{eqnarray*}$$
  
  
• Como la asignación $\mbox{\boldmath$\epsilon$ }$ satisface a cada una de las cláusulas c_i tenemos que para toda G_i uno de los vértices ``queda cubierto'', es decir, es el extremo de una arista cuyo otro extremo ha quedado en U. Fijamos pues en cada triángulo G_i un vértice cubierto y los otros dos los incluimos en U.
• Tenemos así un recubrimiento por vértices con K vértices.

Una solución de VC da una solución de 3SAT: Si U es un recubrimiento por vértices con n+2m vértices entonces en cada arista G^j exactamente uno de sus extremos pertenece a U. Hagamos verdadera a la literal correspondiente al extremo en U, en cada G^j. Esta asignación evidentemente satisface a cada cláusula.
Siguiente: Problemas de asignación de Un nivel arriba: Algunos problemas principales completos-NP Anterior: Partición