Problema del camino hamiltoniano
Hay n! diferentes secuencias de vértices que podrían ser caminos hamiltonianos en un grafo de n vértices dado (y lo son, en un grafo completo), por lo que un algoritmo de búsqueda de fuerza bruta que pruebe todas las secuencias posibles sería muy lento.Un primer algoritmo exacto para encontrar un ciclo hamiltoniano en un grafo dirigido fue el algoritmo enumerativo de Martello. Un procedimiento de búsqueda de Frank Rubin divide las aristas del grafo en tres clases: las que deben estar en el camino, las que no pueden estar en el camino y las indecisas. A medida que avanza la búsqueda, un conjunto de reglas de decisión clasifica las aristas indecisas y determina si se debe detener o continuar la búsqueda. El algoritmo divide el gráfico en componentes que pueden resolverse por separado. Además, se puede utilizar un algoritmo de programación dinámica de Bellman, Held y Karp para resolver el problema en tiempo O(n2 2n). 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 los vértices en S y termine en v. Para cada elección de S y v, existe un camino para (S,v) si y sólo si v tiene un vecino w tal que exista un camino para (S – v,w), que puede buscarse a partir de 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 recuento más simple, de contar cubiertas de ciclos, que puede ser resuelto mediante el cálculo de ciertos determinantes matriciales. Utilizando este método, demostró cómo resolver el problema de los ciclos hamiltonianos en grafos arbitrarios de n vértices mediante un algoritmo de Monte Carlo en tiempo O(1,657n); para los grafos bipartitos este algoritmo puede mejorarse aún más hasta el tiempo o(1,415n).
Para los grafos de grado máximo tres, una cuidadosa búsqueda de retroceso puede encontrar un ciclo hamiltoniano (si existe) en tiempo O(1.251n).
Los caminos y ciclos hamiltonianos se pueden encontrar utilizando un solucionador SAT.
Debido a la dificultad de resolver los problemas de caminos y ciclos hamiltonianos en ordenadores convencionales, también se han estudiado en modelos no convencionales de computación. Por ejemplo, Leonard Adleman demostró que el problema del camino hamiltoniano puede resolverse utilizando un ordenador de ADN. Aprovechando el paralelismo inherente a las reacciones químicas, el problema puede resolverse utilizando un número de pasos de reacción química lineal 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 grafo hecha de cables ópticos y divisores de haz que son atravesados por la luz con el fin de construir una solución para el problema. El punto débil de este enfoque es la cantidad de energía requerida, que es exponencial en el número de nodos.