Problema del camino hamiltoniano

En el campo matemático de la teoría de grafos, el problema del camino hamiltoniano y el problema del ciclo hamiltoniano son problemas para determinar si un camino hamiltoniano (un camino en un gráfico dirigido o no dirigido) que visita cada vértice exactamente una vez) o existe un ciclo hamiltoniano en un gráfico dado (ya sea dirigido o no dirigido). Ambos problemas son NP-completos.

El problema del ciclo hamiltoniano es un caso especial del problema del viajante de comercio, obtenido al establecer la distancia entre dos ciudades en una si son adyacentes y dos en caso contrario, y verificando que la distancia total recorrida es igual a n (si es así, la ruta es un circuito hamiltoniano; si no hay un circuito hamiltoniano, la ruta más corta será más larga).

Reducción entre el problema del camino y el problema del ciclo

Los problemas de encontrar un camino hamiltoniano y un ciclo hamiltoniano se pueden relacionar de la siguiente manera:

• En una dirección, el problema del camino Hamiltoniano para el gráfico G puede estar relacionado con el problema del ciclo Hamiltoniano en un gráfico H obtenidas G añadiendo un nuevo vértice universal x, conexión x a todos los vértices G. Así, encontrar un camino Hamiltoniano no puede ser significativamente más lento (en el peor caso, como función del número de vértices) que encontrar un ciclo Hamiltoniano.
• En la otra dirección, el problema del ciclo Hamiltoniano para un gráfico G es equivalente al problema del camino Hamiltoniano en el gráfico H obtenido añadiendo vértices terminales (degree-one) s y t adjunta respectivamente a un vértice v de G y a v', a cleaved copy of v que da v ' el mismo barrio v. El camino Hamiltoniano en H corriendo por los vértices s− − v− − x− − ⋯ ⋯ − − Sí.− − v.− − t{displaystyle s-v-x-cdots -y-v'-t corresponde al ciclo Hamiltoniano en G corriendo v− − x− − ⋯ ⋯ − − Sí.()− − v){displaystyle v-x-cdots -y(-v)}.

Algoritmos

¡Hay n! diferentes secuencias de vértices que podrían ser caminos hamiltonianos en un gráfico de n-vértice dado (y lo son, en un gráfico completo), por lo que un algoritmo de búsqueda de fuerza bruta que prueba todos los posibles las secuencias serían muy lentas. Uno de los primeros algoritmos exactos para encontrar un ciclo hamiltoniano en un gráfico dirigido fue el algoritmo enumerativo de Martello. Un procedimiento de búsqueda de Frank Rubin divide los bordes del gráfico en tres clases: los que deben estar en el camino, los que no pueden estar en el camino y los indecisos. A medida que avanza la búsqueda, un conjunto de reglas de decisión clasifica los bordes indecisos y determina si detener o continuar la búsqueda. El algoritmo divide el gráfico en componentes que se pueden resolver por separado. Además, se puede usar un algoritmo de programación dinámica de Bellman, Held y Karp para resolver el problema en el tiempo O(n² 2ⁿ). En este método, se determina, para cada conjunto S de vértices y cada vértice v en S, si existe un camino que cubra exactamente el vértices en S y termina en v. Para cada elección de S y v, existe una ruta para (S,v) si y solo si v tiene un vecino w tal que existe una ruta para (S − v,w), que se puede consultar a partir de la información ya calculada en el programa dinámico.

Andreas Björklund proporcionó un enfoque alternativo utilizando el principio de inclusión-exclusión para reducir el problema de contar el número de ciclos hamiltonianos a un problema de conteo más simple, de contar las coberturas de los ciclos, que se puede resolver calculando ciertos determinantes de matriz. Usando este método, mostró cómo resolver el problema del ciclo hamiltoniano en gráficos arbitrarios de n-vértice mediante un algoritmo de Monte Carlo en el tiempo O(1.657ⁿ); para gráficos bipartitos, este algoritmo se puede mejorar aún más al tiempo o(1.415ⁿ).

Para gráficos de máximo grado tres, una búsqueda cuidadosa de retroceso puede encontrar un ciclo hamiltoniano (si existe) en el tiempo O(1.251ⁿ).

Los caminos y ciclos hamiltonianos se pueden encontrar utilizando un solucionador SAT.

Debido a la dificultad de resolver los problemas de ruta y ciclo hamiltonianos en computadoras convencionales, también se han estudiado en modelos no convencionales de computación. Por ejemplo, Leonard Adleman demostró que el problema de la ruta hamiltoniana puede resolverse usando una computadora de ADN. Explotando el paralelismo inherente a las reacciones químicas, el problema puede resolverse utilizando una serie de pasos de reacción química lineales en el número de vértices del gráfico; sin embargo, requiere un número factorial de moléculas de ADN para participar en la reacción.

También se ha propuesto una solución óptica al problema hamiltoniano. La idea es crear una estructura similar a un gráfico hecha de cables ópticos y divisores de haz que son atravesados por la luz para construir una solución al problema. El punto débil de este enfoque es la cantidad de energía requerida que es exponencial en el número de nodos.

Complejidad

El problema de encontrar un ciclo o camino hamiltoniano está en FNP; el problema de decisión análogo es probar si existe un ciclo o camino hamiltoniano. Los problemas del ciclo hamiltoniano dirigido y no dirigido fueron dos de los 21 problemas NP-completos de Karp. Siguen siendo NP-completos incluso para tipos especiales de gráficos, como:

• bipartitas gráficas,
• gráficos plano no redirigidos del grado máximo tres,
• gráficos planar dirigidos con indegree y outdegree a la mayoría de dos,
• gráficos bipartitas sin puente,
• Gráficos bipartitas 3-conectados,
• subgraphs of the square grid graph,
• Subgrafos cúbicos del gráfico de la cuadrícula cuadrada.

Sin embargo, para algunas clases especiales de gráficos, el problema se puede resolver en tiempo polinomial:

• Los gráficos planares conectados siempre son Hamiltonian por un resultado debido a Tutte, y la tarea computacional de encontrar un ciclo Hamiltoniano en estos gráficos se puede llevar a cabo en tiempo lineal computando un llamado camino Tutte.
• Tutte demostró este resultado mostrando que cada gráfico planar conectado contiene un camino Tutte. Las trayectorias de tutte a su vez pueden ser calculadas en tiempo cuadrático incluso para gráficos planificados conectados, que pueden utilizarse para encontrar ciclos Hamiltonianos y ciclos largos en generalizaciones de gráficos plano.

Al juntar todas estas condiciones, queda abierto si los gráficos planos bipartitos 3-regulares conectados en 3 deben contener siempre un ciclo hamiltoniano, en cuyo caso el problema restringido a esos gráficos no podría ser NP-completo; ver la conjetura de Barnette.

En gráficos en los que todos los vértices tienen un grado impar, un argumento relacionado con el lema del apretón de manos muestra que el número de ciclos hamiltonianos a través de cualquier borde fijo siempre es par, por lo que si se da un ciclo hamiltoniano, entonces también debe existir un segundo.. Sin embargo, encontrar este segundo ciclo no parece ser una tarea computacional sencilla. Papadimitriou definió la clase de complejidad PPA para encapsular problemas como este.