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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.