Instance hardness: one bit makes all the difference

The Hamiltonian cycle problem 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.

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 Joeri Sleegers wanted more than that. 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 [1]. “So we define  ‘fitness’ as ‘hardness’.” says Joeri Sleegers, “ and hardness is measured as the runtime it takes for the best know backtracking algorithm, known as Vandegriend-Culberson. After that, we just have to let computational evolution perform its magic, and voila, there’s your answer!”

Evolutionary algorithm

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 were 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  is also  a nominee for the best paper award at ECTA20. It is Joeri’s 4^th publication as a UvA-student, and one more is currently under development [1][2][3][4][5].

ECTA’20 will be held 2-4 November 2020.

References:

[1] “Looking for the Hardest Hamiltonian Cycle Problem Instances” Joeri Sleegers and Daan van den Berg, IJCCI 2020: Proceedings of the 12th International Joint Conference on Computational Intelligence.

[2] “A Predictive Data Analytic for the Hardness of Hamiltonian Cycle Problem Instances” G. van Horn, R. Olij, J. Sleegers, D. van den Berg, DATA ANALYTICS 2018 : The Seventh International Conference on Data Analytics …

[3] “Plant Propagation & Hard Hamiltonian Graphs” J. Sleegers, D. van den Berg, EvoStar 2020

[4] “Where the really hard problems aren’t” J. Sleegers, R. Olij, G. van Horn, D. van den Berg, Operations Research Perspectives 7, 100160

[5] “Almost Squares in Almost Squares: Solving the Final Instance” D. van den Berg, F. Braam, M. Moes, E. Suilen, S. Bhulai, DATA ANALYTICS 2016, 81