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/… Commented Apr 12, 2019 at 12:19
• Thanks a lot! But I cannot open this link after some times trying ... Is this link correct? Thanks again! Commented Apr 12, 2019 at 12:37
• it works for me... Commented Apr 12, 2019 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". Commented Apr 12, 2019 at 14:57
• Yes! Thanks! I have edited the title just now. Commented Apr 13, 2019 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.

For random graphs, there are algorithms that are efficient on average. See for example A fast algorithm on average for solving the Hamilton Cycle problem by Michael Anastos and the references therein.

If you have a particular graph which seems to be hard to handle, then you could try Concorde, which is carefully designed program for solving the traveling salesman problem (which of course is closely related to the Hamiltonian cycle problem).

Another way to tackle hard instances is to try solvers that have been designed to solve the FHCP Challenge Set. You can use Google Scholar to find papers that cite this one; that should point you to some good solving algorithms. (EDIT: I see now that FHCP was mentioned in another answer.)

The most efficient exact algorithm for finding Hamilton paths and circuits is "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21 (Oct. 1974), pp 576-580; DOI: 10.1145/321850.321854.

• Let me disclose that you are the author of the article that you are citing. Commented Mar 28 at 9:34
• On MathOverflow, when citing a paper of one's own, it is customary to explicitly disclose that it is a paper of one's own. Commented Mar 28 at 20:58
• I thought that my name would be posted automatically, and I see it there twice following that post. Commented Mar 29 at 17:59