DIR Return Create A Forum - Home
---------------------------------------------------------
knight tours
HTML https://knighttours.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: general Hamiltonian cycles problem
*****************************************************
#Post#: 53--------------------------------------------------
hard Hamiltonian graphs
DIR By: gsgs
Date: July 22, 2026, 12:23 am
---------------------------------------------------------
graphs that are hard to solve for the Hamiltonian-Cycle-Solvers
are easily constructed , if the graph is non-Hamiltonian.
Take some parity-like constraint, that can't be satisfied.
E,g, bipartite graphs, where the sizes of the parts don't match
as e.g. in n*n knight's tours where n is odd.
Hard Hamiltonian graphs are not so easy to construct.
Random graphs are easy.
The 58 smallest graphs in the FHCP-challenge set (<400 vertices)
are easily solved in <1 second by Clingo or Kissat.
The X9-graphs from another thread here are solved in 1 second
for n<700 vertices.
So, what is the smallest Hamiltonian graph m that no solver
can solve in < 1 second ?
here is my smallest (by # vertices) Hamiltonian graph
that no hcp-solver can solve in < 1 second on 1 thread .
HTML http://magictour.free.fr/hard102.adj
it has 102 vertices , 526 edges , maximal border-size = 25
and is maximal uniquely Hamiltonian
the average times needed to find the hc in 1000 random
isomorphic graphs on my Ryzen 7 are
10.0 , clingo
10.8 , kissat
>200 , chalat, restarted chalat
? , SLH (with wine in Linux)
17.0 , restarted SLH
25.0 , minmax bordersize
ptourgl
-------------------------------------
here a 77-vertex-graph made from the 102-vertex graph above :
httpL//magictour.free.fr/har77c.ahc
77 vertices,565 edges,maximal uniquely hamiltonian
the average times needed to find the hc in 1000 random
isomorphic graphs on my Ryzen 7 are
4.75 , clingo
5.28 , kissat
110,32.8 , chalat, restarted chalat
? , SLH (with wine in Linux)
7.10 , restarted SLH
22.0 , minmax bordersize
chalat = Chalaturnyk,2009
SLH = snake and ladder heuristics,2013
kissat = Kissat 4.0 with Chinese Remainder Encoding (Heule)
clingo = clingo 5.4.1 , 2020
my Ryzen 9 at 5 GHz was almostdouble as fast, before it died
2026
------------------------------------------------
if you have a solver than can solve this in < 1s , please tell
us !
if you have a smaller one, please post it here !
#Post#: 54--------------------------------------------------
Re: hard Hamiltonian graphs
DIR By: gsgs
Date: August 15, 2026, 6:18 pm
---------------------------------------------------------
Liu Liu and Truszczinsky were looking for hard HCP-benchmarks
in 2019 and came up with grid-digraphs with randomly deleted
arcs.
They give a list of 784 digraphs, including 235 Hamiltonan ones
with 12x14=168 vertices.
When converted to undirected graphs they have 504 vertices
and clingo needs >1000 seconds per graph , Kissat with
Chinese Remainder encoding needs 60s per graph.
But SLH with timelimit 1s solves them easily
HTML https://arxiv.org/pdf/1909.08252
--------------------------------------------------
----------------------------------------
average time in seconds needed to find a hc (wazir-tour) in 1000
randomly
vertex-permuted full undirected grid-graphs
clingo ; kisat ; slh ; cha
--------------------------------------------------------------------
10x10, .542(177),0.3 ; .310( 64),.31 ; ??? .002(34) ; .125 769
.011
12x12, 21.9(174),4.0 ; 1.91( 98),1.9 ; ??? .004(29) ; 19.5 490
.018
14x14, 412(214),5.0 ; 12.6(141),9.3 ; ??? .007(28) ; ???
237'317 .036/.255
16x16,
time in s
100 * standard deviation / expectation value of the times
time with random restart
grid-graphs , easy for humans , are surprisingly hard for
clingo,kissat,chalat , but easy for slh .
there is a phase transition when deleting about 20% of edges
randomly
in undirected rextangular gridgraphs with some hard instances ,
except for slh
#Post#: 55--------------------------------------------------
Re: hard Hamiltonian graphs
DIR By: gsgs
Date: August 15, 2026, 6:34 pm
---------------------------------------------------------
here they give hard nonhamiltonian digraphs with just 40,50,60
vertices:
HTML https://cse.hkust.edu.hk/assat/hardsat.html
But they are hard for SAT-solvers only with the chosen
SAT-encoding. They contain a vertex with outdegree 0 ,
so they are easy for HCP-solvers
They were included in SAT-competition 2018 and in the
2022 anniversary track.
HTML http://webdocs.cs.ualberta.ca/~mmueller/ps/2018/2018-SAT-competition-GrandTour.pdf
#Post#: 56--------------------------------------------------
Re: hard Hamiltonian graphs
DIR By: gsgs
Date: August 15, 2026, 8:33 pm
---------------------------------------------------------
for the Knuth benchmarks in
HTML https://www-cs-faculty.stanford.edu/~knuth/fasc8a.ps.gz
page 16 (page 22 into the .pdf)
page 41 (47 into the .pdf)
The nonhamiltonian Grinberg graph with 268 vertices is hard
for some solvers
Kissat with CRE-encoding solves it in 2312 s
It has low treewidth , min. bordersize <=13 , so ptourg solves
it in 2s
The Fleischner graphs, also mentioned in
HTML https://arxiv.org/pdf/1806.09285
are easy for clingo
#Post#: 57--------------------------------------------------
Re: hard Hamiltonian graphs
DIR By: gsgs
Date: August 15, 2026, 8:44 pm
---------------------------------------------------------
Connelly in
HTML https://research-repository.st-andrews.ac.uk/bitstream/handle/10023/2533/AbramConnellyPhDThesis.pdf?sequence=3&isAllowed=y
constructs hard random graphs with phase transition at
HTML https://research-repository.st-andrews.ac.uk/bitstream/handle/10023/2533/AbramConnellyPhDThesis.pdf?sequence=3&isAllowed=y
still hard despite surprisingly many random edges.
But he only tested them with the old Vandegriend/Culberson
solver
while they are easy for clingo
#Post#: 58--------------------------------------------------
Re: hard Hamiltonian graphs
DIR By: gsgs
Date: August 15, 2026, 8:55 pm
---------------------------------------------------------
the FHCP-challenge set here
HTML https://sites.flinders.edu.au/flinders-hamiltonian-cycle-project/fhcp-challenge-set/
is probably the currently most useful collection of
hard Hamiltonian graphs.
They have 1001 graphs with 66-9528 vertices
171 of them with <1000 vertices
here a list of the graphs and their properties and running times
:
HTML http://magictour.free.fr/999.F28
*****************************************************
Page 1 of 1