4
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 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, 2014 at 1:49
  • $\begingroup$ This is not bad: webdocs.cs.ualberta.ca/~joe/Theses/HCarchive/main.html $\endgroup$
    – joro
    Oct 20, 2014 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, 2020 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, 2020 at 16:40

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

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.