# Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?

I am not expertise in graph theory. So have to ask this question here. The term "good" means that the algorithms should be efficient for general undirected simple connected graphs with a higher success probability.

I also read the question Efficient Hamiltonian cycle algorithms for graph classes.

But it does answer my concern.

• You will need to be more specific for a helpful answer. Here is a list of resources you might want to consult: web.archive.org/web/20100324030526/http://alife.ccp14.ac.uk/… – Carlo Beenakker Apr 12 '19 at 12:19
• Thanks a lot! But I cannot open this link after some times trying ... Is this link correct? Thanks again! – Licheng Wang Apr 12 '19 at 12:37
• it works for me... – Carlo Beenakker Apr 12 '19 at 12:49
• Does "needless a circle" mean that the Hamiltonian path need not be a cycle? If so, probably "not necessarily" is clearer than "needless". – LSpice Apr 12 '19 at 14:57
• Yes! Thanks! I have edited the title just now. – Licheng Wang Apr 13 '19 at 1:11

The Hamiltonian path problem is NP-complete in general, so only heuristics could exist if P≠NP.

The rotation-extension heuristic may be the simplest heuristic:

Input: undirected graph G with size n
Let P be a path
Let e be a random edge of G
P:=[e]
Loop:
If Extension(G,P)≠∅:
P:=Extension(G,P)
Goto Loop
Let Π be the family of the Posa extensions¹ of P in G
For π in Π:
If Extension(G,π)≠∅:
P:=Extension(G,π)
Goto Loop
{Remark: The heuristic is not able to extend the path, so we must stop}
If P is a hamiltonian path, return P, otherwise stop without returning anything.

Subprocedure: Extension
Input: undirected graph G and a path P⊆G
For x in vertices of G:
if x is connected with one of P's endpoints p:
Return P+(p,x)
Return ∅

1: as defined in https://www.sciencedirect.com/science/article/pii/S0012365X06005097


In other words, the program finds extensions and extensions after rotations until there're none, and return a hamiltonian path if there is one.

For more sophiscated heuristics, one can use methods from the Flinders Hamiltonian Cycle Project.