What is the best Hamiltonian Cycle Problem (HCP) solvers available in the market? Googling so far shows that there is one created by Flinders University that can solve at most 5000 node instances.

I know HCP is a NP-hard problem but is 5000 node the best that researchers can produce so far? Is no researcher / commercial entity interested in producing a better one (maybe solve 50000 node instances?) because a HCP is non-monetizable unless it can solve billions node instances (crack RSA and what nots)?

  • 6
    $\begingroup$ TSP is more general/applicable, and there are good TSP solvers like Concorde. It has been used to solve 85,900-node "real-life" instances, but it cannot prove optimality for much smaller but tougher instances. $\endgroup$ – Austin Buchanan Oct 19 '14 at 1:49
  • $\begingroup$ This is not bad: webdocs.cs.ualberta.ca/~joe/Theses/HCarchive/main.html $\endgroup$ – joro Oct 20 '14 at 13:25
  • $\begingroup$ If G is a graph with p greater than or equal to 3 vertices and sigma greater than or equal to p÷2 G is hamiltonian $\endgroup$ – Kalai Sep 13 at 11:41
  • $\begingroup$ For small instances one can try to use integer programming solver and see if it works. Assume it will vary wildly based on the instance. $\endgroup$ – Chandra Chekuri Sep 13 at 16:40

I found myself having to find a Hamilton path in a graph of 200 vertices (what you called "nodes"). My first idea was to use the Hamilton path solver in Maxima ( http://maxima.sourceforge.net/docs/manual/de/maxima_50.html#IDX2257 ), but it wasn't able to solve it. Luckily, a few years ago, I used to use SAT solvers to solve difficult logic grid puzzles (because I had a friend who kept on sending them to me!), so wrote a program to write a SAT model for the graph. To my delight, when I fed the model to an open source SAT solver (MiniSat), it was able to resolve it in less than 10 minutes (I didn't time it I'm afraid - I started it, and it had finished when I came back).

Disclaimer: I am not a "theoretical computer scientist", nor even somebody who has ever done a Hamilton cycle before - I landed here after a Google search and thought I'd share what I did over the weekend. However, for a beginner, beating the mathematicians who wrote the Graphs package in Maxima isn't bad - and suggests that if you need to find a Hamilton path (or cycle) in a large graph, building a SAT model is an approach worth considering.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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