1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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/… $\endgroup$ Apr 12, 2019 at 12:19
  • $\begingroup$ Thanks a lot! But I cannot open this link after some times trying ... Is this link correct? Thanks again! $\endgroup$ Apr 12, 2019 at 12:37
  • $\begingroup$ it works for me... $\endgroup$ Apr 12, 2019 at 12:49
  • 2
    $\begingroup$ Does "needless a circle" mean that the Hamiltonian path need not be a cycle? If so, probably "not necessarily" is clearer than "needless". $\endgroup$
    – LSpice
    Apr 12, 2019 at 14:57
  • $\begingroup$ Yes! Thanks! I have edited the title just now. $\endgroup$ Apr 13, 2019 at 1:11

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

New contributor
Frank Rubin is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
  • 6
    $\begingroup$ Let me disclose that you are the author of the article that you are citing. $\endgroup$
    – Alex M.
    12 hours ago
  • $\begingroup$ 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. $\endgroup$
    – Stefan Kohl
    1 hour ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.