<p>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 ( <a href="http://maxima.sourceforge.net/docs/manual/de/maxima_50.html#IDX2257" rel="nofollow noreferrer">http://maxima.sourceforge.net/docs/manual/de/maxima_50.html#IDX2257</a> ), 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). </p>

<p>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.</p>

CC BY-SA 3.0
2017-09-11T09:32:02.110Z
2017-09-11T09:32:02.110Z
Chris Tennant
<p>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.</p>

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

CC BY-SA 3.0
2014-10-19T01:49:31.027Z
TSP is more general/applicable, and there are good TSP solvers like [Concorde](http://en.wikipedia.org/wiki/Concorde_TSP_Solver). It has been used to solve 85,900-node "real-life" instances, but it cannot prove optimality for much smaller but tougher instances.
Austin Buchanan
CC BY-SA 3.0
2014-10-20T13:25:44.893Z
This is not bad:  http://webdocs.cs.ualberta.ca/~joe/Theses/HCarchive/main.html
joro
CC BY-SA 4.0
2020-09-13T11:41:03.163Z
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
Kalai
CC BY-SA 4.0
2020-09-13T16:40:11.237Z
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.
Chandra Chekuri
<graph-theory><hamiltonian-paths>
Best Hamiltonian Cycle Problem solver
Izzah Leari
# Best Hamiltonian Cycle Problem solver

(Asked by: username_0 on 2014-10-19)

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

**Tags:** graph-theory, hamiltonian-paths

> **Comments:**
> **username_1**: TSP is more general/applicable, and there are good TSP solvers like [Concorde](http://en.wikipedia.org/wiki/Concorde_TSP_Solver). It has been used to solve 85,900-node "real-life" instances, but it cannot prove optimality for much smaller but tougher instances.  
> **username_2**: This is not bad:  http://webdocs.cs.ualberta.ca/~joe/Theses/HCarchive/main.html  
> **username_3**: 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  
> **username_4**: 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.  

---

## 1 answers

### Answer by username_5 on 2017-09-11. Score: 2

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.


---

