Hamiltonian path problem
Er zijn n! verschillende volgordes van hoekpunten die een Hamiltonian path kunnen zijn in een gegeven n-vtex-grafiek (en zijn, in een complete grafiek), dus een brute force-zoekalgoritme dat alle mogelijke volgordes test zou zeer traag zijn.Een vroeg exact algoritme voor het vinden van een Hamiltonian cycle in een gerichte grafiek was het enumeratieve algoritme van Martello. Een zoekprocedure van Frank Rubin verdeelt de randen van de grafiek in drie klassen: die welke in het pad moeten liggen, die welke niet in het pad kunnen liggen, en onbeslist. Naarmate de zoektocht vordert, classificeert een reeks beslisregels de onbesliste randen en bepaalt of de zoektocht moet worden stopgezet of voortgezet. Het algoritme verdeelt de grafiek in componenten die afzonderlijk kunnen worden opgelost. Ook kan een dynamisch programmeringsalgoritme van Bellman, Held, en Karp worden gebruikt om het probleem in tijd O(n2 2n) op te lossen. In deze methode bepaalt men voor elke verzameling hoekpunten S en elk hoekpunt v in S of er een pad is dat precies de hoekpunten in S omvat en eindigt bij v. Voor elke keuze van S en v bestaat een pad voor (S,v) als en slechts als v een buur w heeft zodat een pad bestaat voor (S – v,w), dat kan worden opgezocht uit reeds berekende informatie in het dynamische programma.
Andreas Björklund gaf een alternatieve benadering die gebruik maakt van het inclusie-exclusie principe om het probleem van het tellen van het aantal Hamiltoniaanse cycli te reduceren tot een eenvoudiger telprobleem, het tellen van cycle covers, dat kan worden opgelost door bepaalde matrixdeterminanten te berekenen. Met behulp van deze methode toonde hij aan hoe het Hamiltoniaanse-cyclusprobleem in willekeurige n-vtex-grafieken met een Monte Carlo-algoritme kan worden opgelost in tijd O(1.657n); voor bipartiete grafieken kan dit algoritme verder worden verbeterd tot tijd o(1.415n).
Voor grafieken van maximaal drie graden kan een voorzichtige backtracking-zoekopdracht een Hamiltoniaanse cyclus vinden (als er een bestaat) in tijd O(1.251n).
Hamiltoniaanse paden en cycli kunnen worden gevonden met behulp van een SAT-oplosser.
Omdat het moeilijk is om de Hamiltoniaanse paden- en cyclioproblemen op conventionele computers op te lossen, zijn ze ook bestudeerd in onconventionele modellen van computergebruik. Leonard Adleman heeft bijvoorbeeld aangetoond dat het Hamiltoniaanse padprobleem kan worden opgelost met behulp van een DNA-computer. Door gebruik te maken van het parallellisme dat inherent is aan chemische reacties, kan het probleem worden opgelost met een aantal chemische reactiestappen dat lineair is met het aantal hoekpunten van de grafiek; er is echter een factorieel aantal DNA-moleculen nodig om aan de reactie deel te nemen.
Er is ook een optische oplossing voor het Hamiltoniaanse probleem voorgesteld. Het idee is om een grafiekachtige structuur te maken van optische kabels en bundelsplitsers die door licht worden doorkruist om een oplossing voor het probleem te vinden. Het zwakke punt van deze aanpak is de vereiste hoeveelheid energie, die exponentieel is met het aantal knooppunten.