P/NP: Ciclo Hamiltoneano, Problema del Viajante, Coloreo de Grafos, Subset Sum, Clique

Question 1

Explique el problema del Ciclo Hamiltoneano

Answer 1

Sea G un grafo direccionado, definimos un ciclo C en G como hamiltoneano si:

• Visita cada vértice 1 vez y sólo 1 vez.
• Comienza y termina por el mismo vértice.

Entonces, dado un grafo, se desea saber si existe un ciclo hamiltoneano.

Question 2

Ham-Cycle: ¿Es NP?

Answer 2

Ham-Cycle es NP.

Dado un certificado T que contenga una lista ordenada de vértices, puedo verificar en tiempo polinomial que:

• |T| = |V|
• t_0 = t_|V| (el primer nodo y el último son el mismo)
• Todos los vértices de V están en T
• Para todo par de vértices en T, existe un eje en el grafo.

Por lo tanto, es NP.

Question 3

Ham-Cycle: ¿Es P?

Answer 3

No se conoce un algoritmoq ue resuelva a Ham-Cyle en tiempo polinómico. Si probamos que Ham-Cycle es NP-C, entonces Ham-Cycle sería P si y sólo si P = NP.

Question 4

Explique la reducción de 3SAT a Ham-Cycle

Answer 4

Para I instancias de 3SAT:
- Con n variables x1, ..., xn
- k clàusulas c1, ..., cn

Construiremos un grafo G donde encontrar el ciclo hamiltoneano.

1. Construimos n caminos p1, ..., pn, por donde cada uno representa a una variable.
2. Cada camino estará conformado por 2 * k nodos, unidos entre sí por aristas de ida y vuelta.
3. Uniremos cada camino:

a. Desde su nodo inicial hasta el nodo inicial del camino siguiente.
b. Desde su nodo inicial hasta el nodo final del camino siguiente.
c. Desde su nodo final hasta el nodo inicial del camino siguiente.
d. Desde su nodo final hasta el nodo final del camino siguiente.

4. Creamos nodos s,t y agregamos ejes:

a. s - v1,1 (primero de la primer fila)
b. s - v1,2k (último de la primer fila)
c. vn,1 - t (primero de la última fila)
d. vn,n - t (último de la última fila)
e. t - s

5. Creamos 1 nodo por cada cláusula Ti = (t1, t2, t3).
6. Para cada variable x de la cláusula i:

a. Se unen 2 nodos del camino de la variable x con el nodo de la cláusula i en la posición i*2 y i*2+1. Si la variable no está negada, las direcciones van de nodo a cláusula y luego de cláusula a nodo. Sino, al revés.

Si existe un camino hamiltoneano que parte de s y llega a t (regresando luego a s), y pasando por todos los nodos, entonces hay forma de satisfacer la expresión booleana.

• El sentido por el que se recorre el camino determina si el valor de una variable es 0 ó 1: para la derecha, 1. Para la izquierda, 0.
• El eje seleccionado para acceder al nodo “ cláusula” nos dice qué varible la activa.
• Si una variable requiere estar negada y no estarla para activar varias cláusulas, el ciclo e simposible de construir.

Question 5

Ham-Cycle: ¿Es NP-C?

Answer 5

Ham-Cycle es NP-C.

Como Ham-Cycle pertenece a NP y 3SAT es reducible a HAM-CYCLE, entonces:

Ham-Cycle pertenece a NP-C.

Question 6

Explique el problema del viajante.

Answer 6

Dado:
- n ciudades
- Las distancias entre cada par de ciudades

Queremos determinar si existe un tour o ciclo de distancia total menor a k tal que se recorran las n ciudades.

Question 7

Problema del viajante: ¿Es NP?

Answer 7

El problema del viajante es NP.

Sean n ciudades, las distancias entre cada par de ciudades, T un ceritificado y k la distancia como límite, se puede verificar que:

• T contenga a todas las ciudades sólo 1 vez, y que termine y comience en la misma.
• Que la suma total de la distancia recorrida sea menor a ´k´.

Question 8

Explique la reducción de Ham-Cycle a Viajante.

Answer 8

Sea I una instancia de Ham-Cycle, tenemos un grafo G=(V,E) donde:

• Por cada vértice v, creamos una ciudad vi.
• Por cada arista eij, definimos la distancia d(vi, vj) = 1.
• Aquellas distancias que no están definidas (no tienen aristas) las crearemos con valor 2.
• Ponemos como valor k = |V| (número de vértices).

Solucionamos viajante con k definido. Si existe un camino con longitud k, entonces existe un ciclo hamiltoneano.

Question 9

Problema del viajante: ¿Es NP-C?

Answer 9

Como Ham-Cycle <=p Viajante, entonces el problema del viajante es NP-C.

Question 10

Explique el problema de Coloreo de Grafos.

Answer 10

Sea un grafo G=(V,E) no dirigido, y una función F que le asigna un color a cada vértice; para todo eje e=(u,v) tal que f(u) != f(v)`.

Queremos colorear el grafo tal que nodos que tienen ejes entre sí no tengan el mismo color.

Question 11

¿A qué se define como “número cromático X(G)`?

Answer 11

Definimos al número cromático X(G) como el menor número de colores necesario par colorear un grafo.

Question 12

¿A qué se define como “polinomio cromático?

Answer 12

Definimos polinomio cromático a la ecuación que permite contar el número de maneras en las cuales puede ser coloreado un grafo usando no más de k colores.

Question 13

¿A qué se llama “clase de color” y a qué se llama “conjunto k- partito?

Answer 13

Llamaremos clase de color al subconjutno de vértices coloreados con el mismo color.
Una k-coloración equivale a una partición de nodos en k conjuntos independientes. Si un grafo es k-coloreable, entonces es k- partito.

Question 14

Explique el problema de decisión de Coloreo de Grafos.

Answer 14

Sean:

• G = (V,E) un grafo no dirigido
• k un valor numérico.

Queremos determinar si es posible definir una función de coloreo que utilice k o menos colores.

Question 15

Explique el caso especial del grafo completo

Answer 15

Si el grafo es simple y completo (todos los vértices están comunicados entre sí), se requiere un color por vértice para colorear el grafo.

Podemos saber si es completo si tiene:

|E| = |V| * ( |V| -1 ) / 2

Question 16

Explique el caso especial del grafo bipartito

Answer 16

Un grafo bipartito requiere de sólo 2 colores para colorear el grafo. Podemos usar un algoritmo similar a BFS para colorear el grafo.

Question 17

Coloreo de grafos: ¿Es NP?

Answer 17

Es NP.

Dado un grafo G, una cantidad de k colores, y un certificado T (que para cada vértice le asigna un color), puedo verificar en tiempo polinomial que:

• Todos los nodos de V están en T.
• La cantidad de colores usados en T es menor o igual a k.
• No existe en G dos vértices adyacentes que en T tengan el mismo color.

Por lo que el coloreo de grafos es NP.

Question 18

Explique la reducción de 3SAT a Coloreo de Grafos

Answer 18

Dada una instancia I de 3SAT con k cláusulas y n variables, creamos:

• Diferentes gadgets que serán subgrafos para colorear.
• 1 gadget para las variables.
• 1 gadget por cláusula.

1. Creamos un vértice para cada variable y su negación.
2. Creamos los vértices especiales T, F, y B (true, false y base).
3. Generamos los ejes:

a. Entre vi y ¬vi
b. Entre vi y ¬vi con B
c. T, F, B entre ellas.

Por lo tanto, la variable tendrá True si tiene el mismo color qu eT.

4. Creamos un gadget para cada cláusula.

a. La cláusula ci = (a,b,c) con a,b,c pertenecientes a: {x1, ¬x1, ..., xn, ¬xn}.
b. Las variables de la cláusula corresponden a los nodos creados para las variables. Por ejemplo, si a = x1, el gadget ci,1 se conecta a v1.

El gadget va a tener la forma detallada en la siguiente imagen.

• Los nodos 1, 2, 3, 4 se conectan a T
• Los nodos 1, 2, 6, 5 se conectan entre sí de forma secuencial.
• Hay un eje entre 3 y 6 y entre 4 y 5
• 5 se conecta a F
• Los nodos c1, c3 y c4 de la cláusula se conectan a las variables que contiene: a, b, c.

5. Definimos k=3 para los colores.
6. Si el grafo resultante se puede pintar con 3 colores, entonces la expresión I se puede satisfacer (los nodos correspondientes a las variables con igual color a T deben estar en true).

Entonces, con al menos 1 variable en True de la cláusula i, el subgrafo correspondiente al gadget de la cláusula i se puede colorear con 3 colores.

=> Si se requiere que 1 variable esté negada y sin negar, no se puede colorear el grafo.

Question 19

Resuelva con la reducción de 3SAT a Coloreo de Grafos:

E = (x1,x2,x4) y (not x1, x3, x4)

Answer 19

x1 = 1
x2 = 1
x3 = 1
x4 = 0

Question 20

Resuelva con coloreo de grafos:

Se tiene el grafo:

ejes:
(A,B) (A,D) (B,C) (C,D) (D,E) (D,F) (E,H) (E,G)

¿ Es k coloreable con k = 4?

Answer 20

Lo es.

Question 21

Explique el problema de decisión Subset Sum

Answer 21

Sea un conjunto C = {w1, ..., wn} de número naturales, queremos determinar si existe un subconjunto de C que sume exactamente W.
Es un problema de decisión relacionado con el problema de la mochila.

Question 22

Subset Sum: ¿Es P?

Answer 22

Subset sum no es P.

Usando programación dinámica, se puede resolver en tiempo pseudo polinomial O(Wn). Si representamos W en bits, el algoritmo crece exponencialmente a la cantidad de bits de W. No se conoce una solución polinomial, por lo que Subset Sum no es P.

Question 23

Subset Sum: ¿Es NP?

Answer 23

Es NP.

Dados:

• Un C conjunto de n números naturales.
• W número a sumar
• T certificado con subconjunto de C.

Podemos determinar polinomialmente que:

∑ (ti) = W, para todo ti en C

Por lo tanto, es NP.

Question 24

Subset Sum: ¿Es NP-Hard?

Answer 24

Es NP-Hard, porque se puede reducir 3DM a Subset Sum. De esta forma, probamos que es NP-C. Si es NP-C, es NP-H.

Question 25

Explique el objetivo de la reducción de 3DM a Subset Sum

Answer 25

Sea I una instancia de 3DM con X,Y,Z conjuntos de n elementos, T ⊆ X x Y x Z conjuntos de m triplas.
Queremos representar cada tripla como un vector de bits.

Question 26

Explique la representación Vectorial para la reducción de 3DM a Subset Sum

Answer 26

Usamos vectores de 3 * n bits:

• Los primeros n bits representan los elementos de X
• Los siguientes n representan los elementos de Y
• Los últimos n representan los elementos de Z.

A cada elemento de los conjuntos le asignamos un orden arbitrario de a n.
posx(x), posy(y), posz(z) son las funciones que dado un elemento, retorna su posición en el set.

A cada t = {xi, yi, zi} tripla de T la representamos como un vector de 3n bits con todos los bits en cero, exceptuando los siguientes:

• posx(xi)
• posy(yj) + n
• posz(zk) + 2n

Los valores binarios se invierten para que al calcular luego w_i, la X quede en los bits menos significativos.

Question 27

Explique la transformación en un número entero para la reducción de 3DM a Subset Sum

Answer 27

Cada vector vt se puede representar como un número t en el subconjunto subset sum.

El valor W lo formaremos como el vector con todos los bits en 1.

Para sumar W, tenemos que encontrar aquellos wt que nos den W. Pero no debo elegir 2 o más números con un mismo bit prendido, porque genera un overflow.

Para evitarlo, vamos a representar cada tripla como un número de la siguiente manera:

wt = d^(posx(xi)-1) + d^(posy(yj)+n-1) + d^(posz(zk)+2n-1)

Siendo d la base elegida. Vamos a usar d = m + 1, con m la cantidad de triplas.

Question 28

Subset Sum: ¿Es NP-H?

Answer 28

Se puede reducir 3DM a Subset Sum.

3DM es NP-C (porque 3SAT es NP-C y se puede reducir a 3DM), entonces Subset Sum es NP-C; por lo tanto, es también NP-H.

Question 29

Resuelva: Subset sum:

Sea la instancia de 3DM

X = x1, x2, x3
Y = y1, y2, y3
Z = z1, z2, z3

T = { (x1,y1,z1), (x2,y2,z3), (x3,y3,z1), (x1, y1, z2), (x3,y3,z2), (x1,y3,z2), (x3,y3,z3) }

Answer 29

Resolución

W = 19173961
C = {(x1,y1,z1), (x2,y2,z3), (x3,y3,z2)}

Question 30

Clique: Explique el problema

Answer 30

Sea un grafo G no dirigido, llamaremos clique a un subconjunto V’ incluído (o igual) en V, de vértices tal que para todo par de vértices, existe un eje que los conecta. Es decir, todos los vértices están conectados entre sí.

La cantidad de nodos en V’ determina el tamaño del clique.

Question 31

Clique: Explique el problema de decisión

Answer 31

Dado un grafo G y un valor numérico k positivo, queremos ver si existe un clique de tamaño k en G.

Question 32

Clique: ¿Es NP?

Answer 32

Es NP.

Dado un grafo G, un valor k de tamaño del clique y un certificado T que contiene un subconjutno de nodos de V, se puede verificar en tiempo polinomial que:

• La cantidad de nodos en T es igual a k
• Cada nodo en T está conectado a los otros nodos de T.

Question 33

Clique: ¿Es P?

Answer 33

No es P.
Por fuerza fruta, la complejidad es exponencial.

Question 34

Clique: ¿NP-Hard?

Answer 34

Sí, porque se puede reducir 3SAT a Clique. Como clique es NP-C, entonces es NP-H.

Question 35

Explique la reducción 3SAT a Cliques

Answer 35

Dada una instancia I de 3SAT con k cláusulas y n variables:

• Creamos un nodo por cada variable en una cláusula.
• Por cada par de variables de diferentes cláusulas, creamos un eje entre ellas si no corresponden a la misma variable o negada.
• Buscamos un clique de tamaño k.

Los nodos dentro del clique indican el valor de las variables como “True”. Aquellas que están fuera del clique pueden ser True o False.

Question 36

Resuelva con la reducción 3SAT a Clique:

E = (x1,x2,x4) y (not x1, x3, x4) y (not x2, not x3, x4) y (not x1, x2, not x4)

Answer 36

not x1
x2
x4

Deben estar en true.

(Hay otras opciones posibles)

Resuelto

Question 37

Haga un resumen de todas las reducciones vistas.

Answer 37

• Set cover >= cobertura de vértices >= conj. indep. >= 3SAT
• Subset sum >= 3DM >= 3SAT
• Coloreo >= 3SAT
• Clique >= 3SAT

Recordamos el Teorema de Cook-Levin:

Para todo X perteneciente a NP: X <= 3SAT

Por lo que 3SAT es de los problemas más complejos de resolver en NP.
=> 3SAT pertenece a NP-C.