Problema del camino Hamiltoniano

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).

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.657n); para grafos bipartitos este algoritmo puede ser mejorado en orden O(1.414n).

Por ejemplo, Leonard Adleman mostró que el problema del camino Hamiltoniano puede ser resuelto usando un ordenador ADN.

[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.

[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.