A direct extract from Joeri Sleegers' master's thesis, a paper entitled "Propagation & Hard Hamiltonian Graphs" was published on the EvoSTAR-conference, which was held completely online in April 2020.
In the study, hard Hamiltonian cycle problem instances are created with evolutionary algorithms such as the Plant Propagation Algorithm. A remarkable result is that these graphs are found far away from the Komlós-Szemerédi bound, where the hardest graphs are traditionally found.
"And they look like a hamburger, with a fat layer of well-connected nodes in the middle, and two leaner layers of sparse nodes on either side" says Joeri Sleegers. "All we need now is ketchup!"
But it won't take long for reality to catch up, warns supervisor Daan van den Berg. Even though the solving algorithm outperforms all major backtracking algorithms, the 'no free lunch theorem' states that no single algorithm can outperform all others on all instances. "But if not free, maybe there's some cheap lunches out there. My guess is with hamburgers."
"The next step is to find out whether we can find some generality in these results. We want the absolute hardest graphs, not second best. Evolutionary algorithms have a mixed reputation where it comes to optimization, but Joeri and I have some tricks up our sleeves for producing evidence. We'll see what comes out."