Problema del camino Hamiltoniano

Existe una relación simple entre los problemas de encontrar un camino de Hamilton y un ciclo Hamiltoniano. En una dirección, el problema del camino Hamiltoniano para el grafo G es equivalente al problema ciclo Hamiltoniano en un grafo H obtenido de G mediante la adición de un nuevo vértice y de la conexión a todos los vértices de G. Por lo tanto, la búsqueda de un camino de Hamilton no puede ser significativamente más lenta (en el peor de los casos, como una función del número de vértices) que encontrar un ciclo de Hamilton.

En la otra dirección, un grafo G tiene un ciclo de Hamilton utilizando la arista uv y solo si el grafo H es obtenido por G mediante la sustitución de la arista por un par de vértices de grado 1, uno conectado a u y el otro conectado a v, tiene un camino de Hamilton. Por lo tanto, al tratar esta sustitución para todas las aristas incidentes hasta cierto vértice seleccionado de G, el problema del ciclo Hamiltoniano puede ser resuelto como máximo por n cálculos en la mayoría de los caminos Hamiltonianos, donde n es el número de vértices en el grafo.

El problema del Ciclo hamiltoniano es también un caso especial del Problema del viajante, obtenido mediante el establecimiento de la distancia entre dos ciudades a uno si son adyacentes y dos en otro caso, y la verificación de que la distancia total recorrida es igual a n (si es así, la ruta es un circuito hamiltoniano; si no hay circuito Hamiltoniano a continuación entonces la ruta más corta será más larga).

Hay n! diferentes secuencias de vértices que pueden ser caminos Hamiltonianos dado un grafo de n vértices (y son, en un grafo completo), por lo que un algoritmo de búsqueda de fuerza bruta que pone a prueba todas las posibles secuencias serían muy lento. Hay varios enfoques más rápidos. Un procedimiento de búsqueda por Frank Rubin[2] divide a las aristas del grafo en tres clases: los que deben estar en el camino, los que no pueden estar en el camino, e indecisos. A medida que procede la búsqueda, un conjunto de reglas de decisión que clasifica las aristas indecisas, y determina si se debe detener o continuar la búsqueda. El algoritmo divide el grafo en componentes que pueden ser resueltas por separadas. Además, un algoritmo de programación dinámica de Bellman, Held, y Karp puede ser utilizado para resolver el problema en un 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 cubre exactamente los vértices en S y termina en v. Para cada elección de S y v, existe un camino para (S,v) si y solo si v tiene un vecino w tal que existe un camino para (S - v,w), que puede ser visto de la información ya calculada en la solución dinámica.[3][4]

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 cubiertas del ciclo, que puede ser resuelto mediante el cálculo de ciertos determinantes. El uso de este método, se mostró cómo resolver el problema del ciclo Hamiltoniano en los grafos n-vértices arbitrarios mediante un Algoritmo de Monte Carlo en orden O(1.657ⁿ); para grafos bipartitos este algoritmo puede ser mejorado en orden O(1.414ⁿ).[5]

Para grafos de máximo grado tres, una búsqueda cuidadosa puede dar marcha atrás y encontrar un ciclo de Hamilton (si existe) en orden O(1.251ⁿ).[6]

Debido a la dificultad de resolver el camino de Hamilton y problemas del ciclo en los equipos convencionales, también se han estudiado en modelos poco convencional de la computación. Por ejemplo, Leonard Adleman mostró que el problema del camino Hamiltoniano puede ser resuelto usando un ordenador ADN. Explotar el paralelismo inherente en las reacciones químicas, el problema puede ser resuelto utilizando un número de etapas de reacción químicas lineales en el número de vértices delgrafo, sin embargo, se requiere un número factorial de distintos tipos de molécula de ADN de participar en la reacción.[7]

El problema de encontrar un ciclo de Hamilton o el camino se encuentra en FNP; el problema de decisión análogo es para probar si existe un ciclo de Hamilton o el camino. Los problemas del ciclo Hamiltonianos dirigidos y no dirigidos, fueron dos de 21 problemas NP-completos de Karp. Permanecen NP-completo incluso para grafos planares no dirigidos de grado máximo tres,[8] para grafos planares dirigidos con grado de entrada y grado de salida como máximo dos,[9] para grafos bipartitos,3-regulares planares no dirigidos sin puente, 3-conexo grafos bipartitos 3-regulares.[10] Sin embargo, poner todas estas condiciones en conjunto, que permanece abiertas si grafos planares bipartitos 3-3-regulares conexos siempre debe contener un ciclo de Hamilton, en cuyo caso el problema restringido a estos grafos no podría ser NP-completos; véase la conjetura de Barnette.

En los grafos en los cuales todos los vértices tienen grado impar, un argumento relacionado con el lema del apretón de manos handshaking lemma muestra que el número de ciclos hamiltonianos a través de cualquier arista fijada, siempre es par, por lo tanto, en caso de que exista un ciclo de Hamilton, también debe existir un segundo ciclo.[11] Sin embargo, la búsqueda de este segundo ciclo no parece ser una tarea computacional sencilla. Papadimitriou definió la clase de complejidad PPA para encapsular problemas semejantes a este.[12]