Hamiltonian cycle problem
His work studies the Hamiltonian cycle problem, which entails finding a route of connections through a network visiting every node exactly once. The problem is NP-complete, meaning that there is no fast algorithm available, and large networks (say 10,000 nodes) are therefore typically undecidable for having a Hamiltonian cycle. For such large networks, all the computers on earth combined cannot find an answer within the lifetime of the future universe.

Pruning procedures
Nonetheless, there are some really good backtracking algorithms that provide some perspective. Typically, they still take ages to run as networks get bigger (proportional to O(n!) milliseconds for a network of n nodes), but by clever algorithmic enhancements known as pruning procedures, more than 90% of the networks still gets done within a reasonable amount of time.

Plant propagation algorithm
But even if the majority of the networks are easily solvable, there’s still a small percentage that ruins the party. Pursuing the question what those really hard problem instances look like, he built an evolutionary algorithm known as the plant propagation algorithm which ‘evolves’ networks to be as fit as possible.
 “So we define  ‘fitness’ as ‘hardness’.” says Joeri Sleegers, “ and hardness is measured as the runtime it takes for the best known backtracking algorithm, which is Vandegriend-Culberson. After that, we just have to let computational evolution perform its magic.

Not as simple as that
Unfortunately, things did not turn out to be as simple as that. First of all, every fitness assessment of every mutation for every single network during the evolutionary process takes almost a day to complete. “this is because we're really pushing the boundary” says Daan van den Berg “we’re looking for the hardest of the hardest problem instances and the harder they get, the longer the evaluation takes.” Second, the number of Hamiltonian networks is much, much larger than the number of nonHamiltonian networks. That makes the number of applicable mutations much bigger. The evolutionary algorithm has to survey a much larger search space.

“Like real evolution, evolutionary algorithm take a lot of time to produce results of which we can only hope they are optimal” says Van den Berg. “Still, these results are encouraging. They suggest that very easy and very hard instances are separated by only one bit of information.”

Joeri’s work “Looking for the Hardest Hamiltonian Cycle Problem Instances” was published at ECTA2020, and is winner of the best paper award. It is Joeri’s 4^th publication as an UvA-student, and one more is currently under development.