Problema do caminho Hamiltoniano
Existem n! diferentes sequências de vértices que podem ser caminhos Hamiltonianos num dado gráfico n-vertex (e estão, num gráfico completo), por isso um algoritmo de pesquisa de força bruta que testa todas as sequências possíveis seria muito lento.Um algoritmo exacto precoce para encontrar um ciclo Hamiltoniano num gráfico dirigido foi o algoritmo enumerativo de Martello. Um procedimento de pesquisa de Frank Rubin divide as margens do gráfico em três classes: as que devem estar no caminho, as que não podem estar no caminho, e as indecisas. À medida que a pesquisa prossegue, um conjunto de regras de decisão classifica os bordos indecisos, e determina se a pesquisa deve ser interrompida ou continuada. O algoritmo divide o gráfico em componentes que podem ser resolvidos separadamente. Além disso, um algoritmo de programação dinâmica de Bellman, Held, e Karp pode ser utilizado para resolver o problema no tempo O(n2 2n). Neste método, determina-se, para cada conjunto S de vértices e cada vértice v em S, se existe um caminho que cobre exactamente os vértices em S e termina em v. Para cada escolha de S e v, existe um caminho para (S,v) se e só se v tiver um vizinho w tal que exista um caminho para (S – v,w), que pode ser procurado a partir de informação já computada no programa dinâmico.
Andreas Björklund forneceu uma abordagem alternativa utilizando o princípio da inclusão-exclusão para reduzir o problema da contagem do número de ciclos Hamiltonianos a um problema de contagem mais simples, de coberturas de ciclos de contagem, que pode ser resolvido através do cálculo de certos determinantes matriciais. Usando este método, mostrou como resolver o problema do ciclo Hamiltoniano em gráficos n-vertex arbitrários através de um algoritmo Monte Carlo no tempo O(1.657n); para gráficos bipartidos, este algoritmo pode ser melhorado para o tempo o(1.415n).
Para gráficos de grau máximo três, uma pesquisa cuidadosa de retrocesso pode encontrar um ciclo Hamiltoniano (se existir) no tempo O(1.251n).
Caminhos e ciclos Hamiltonianos podem ser encontrados usando um solver SAT.
Devido à dificuldade de resolver o caminho Hamiltoniano e problemas de ciclos em computadores convencionais, também foram estudados em modelos não convencionais de computação. Por exemplo, Leonard Adleman mostrou que o problema do caminho Hamiltoniano pode ser resolvido utilizando um computador de ADN. Explorando o paralelismo inerente às reacções químicas, o problema pode ser resolvido utilizando um número de passos de reacção química linear no número de vértices do gráfico; contudo, é necessário um número factorial de moléculas de ADN para participar na reacção.
Foi também proposta uma solução óptica para o problema hamiltoniano. A ideia é criar uma estrutura semelhante a um gráfico feito a partir de cabos ópticos e divisores de feixe que são atravessados pela luz, a fim de construir uma solução para o problema. O ponto fraco desta abordagem é a quantidade de energia necessária, que é exponencial no número de nós.