Prueba de que el ciclo hamiltoniano es NP-Completo

Requisito previo: NP-Completitud , ciclo hamiltoniano .

Ciclo hamiltoniano: un ciclo en un gráfico no dirigido G = (V, E) que atraviesa cada vértice exactamente una vez.

Declaración del problema: dado un gráfico G (V, E), el problema es determinar si el gráfico contiene un ciclo hamiltoniano que consta de todos los vértices que pertenecen a V.
Explicación:
una instancia del problema es una entrada especificada para el problema. Una instancia del problema del Conjunto Independiente es una gráfica G (V, E), y el problema es verificar si la gráfica puede tener un Ciclo Hamiltoniano en G.
Dado que un problema NP-Completo, por definición, es un problema que es a la vez en NP y NP-duro, la prueba de la afirmación de que un problema es NP-Completo consta de dos partes:

1. El problema en sí está en la clase NP.
2. Todos los demás problemas en la clase NP pueden ser reducibles en tiempo polinomial a eso.
   (B es reducible en tiempo polinomial a C se denota como )

Si solo se cumple la segunda condición, el problema se llama NP-Hard .

Pero no es posible reducir cada problema NP a otro problema NP para mostrar su NP-Completitud todo el tiempo. Es por eso que si queremos mostrar que un problema es NP-Completo, simplemente mostramos que el problema está en NP y si cualquier problema NP-Completo es reducible a eso, entonces hemos terminado, es decir, si B es NP-Completo y para C en NP, entonces C es NP-Completo.

1. El ciclo hamiltoniano está en NP
   Si cualquier problema está en NP, entonces, dado un ‘certificado’ , que es una solución al problema y una instancia del problema (un gráfico G y un entero positivo k, en este caso), haremos poder verificar (comprobar si la solución dada es correcta o no) el certificado en tiempo polinomial.
   El certificado es una secuencia de vértices que forman el ciclo hamiltoniano en el gráfico. Podemos validar esta solución comprobando que todos los vértices pertenecen al grafo y cada par de vértices pertenecientes a la solución son adyacentes. Esto se puede hacer en tiempo polinomial, es decir O(V +E) usando la siguiente estrategia para el gráfico G(V, E):

   flag=true
   For every pair {u, v} in the subset V’:
       Check that these two have an edge between them
       If there is no edge, set flag to false and break
   If flag is true:
       Solution is correct
   Else:
       Solution is incorrect
   

2. El ciclo hamiltoniano es NP-difícil
   Para demostrar que el ciclo hamiltoniano es NP-difícil, tendremos que reducir un problema NP-difícil conocido a este problema. Realizaremos una reducción del problema del Camino Hamiltoniano al problema del Ciclo Hamiltoniano.
   Cada instancia del problema del camino hamiltoniano que consta de un gráfico G = (V, E) como entrada se puede convertir en un problema del ciclo hamiltoniano que consta del gráfico G’ = (V’, E’) . Construiremos el grafo G’ de la siguiente forma:
   • V’ = Suma los vértices V del grafo original G y agrega un vértice adicional V _nuevo tal que todos los vértices conectados del gráfico estén conectados a este vértice. El número de vértices aumenta en 1, V’ =V+1 .
   • E’ = Agregar aristas E del gráfico original G y agregar nuevas aristas entre el vértice recién agregado y los vértices originales del gráfico. El número de aristas aumenta con el número de vértices V, es decir, E’=E+V .

   El nuevo grafo G’ se puede obtener en tiempo polinomial, agregando nuevas aristas al nuevo vértice, lo que requiere tiempo O(V). Esta reducción puede probarse mediante las dos afirmaciones siguientes:

   • Supongamos que el gráfico G contiene un camino hamiltoniano que cubre los V vértices del gráfico que comienza en un vértice aleatorio, digamos V _comienza y termina en Vend, ya que conectamos todos los vértices a un nuevo vértice arbitrario V _nuevo en G’.
     Extendemos el camino hamiltoniano original a un ciclo hamiltoniano usando las aristas V _final a V _nuevo y V _nuevo a V _inicio respectivamente. El gráfico G’ ahora contiene el ciclo cerrado que atraviesa todos los vértices una vez.
   • Suponemos que el gráfico G’ tiene un ciclo hamiltoniano que pasa por todos los vértices, incluido V _nuevo . Ahora, para convertirlo en un camino hamiltoniano , eliminamos las aristas correspondientes al vértice V _nuevo en el ciclo. El camino resultante cubrirá los vértices V del gráfico y los cubrirá exactamente una vez.

Así podemos decir que el gráfico G’ contiene un ciclo hamiltoniano si y sólo si el gráfico G contiene un camino hamiltoniano . Por lo tanto, cualquier instancia del problema del ciclo hamiltoniano se puede reducir a una instancia del problema del camino hamiltoniano . Por lo tanto, el ciclo hamiltoniano es NP-Hard .

Conclusión: Dado que el ciclo hamiltoniano es tanto un NP-Problem como un NP-Hard . Por lo tanto, es un problema NP-Completo .