The Hardest Hamiltonian Cycle Problem Instances: The Plateau of Yes and the Cliff of No

Joeri Sleegers, Daan van den Berg*

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We use two evolutionary algorithms to make hard instances of the Hamiltonian cycle problem. Hardness (or ‘fitness’), is defined as the number of recursions required by Vandegriend–Culberson, the best known exact backtracking algorithm for the problem. The hardest instances, all non-Hamiltonian, display a high degree of regularity and scalability across graph sizes. These graphs are found multiple times through independent runs, and by both evolutionary algorithms, suggesting the search space might contain monotonic paths towards the global maximum. For Hamiltonian-bound evolution, some hard graphs were found, but convergence is much less consistent. In this extended paper, we survey the neighbourhoods of both the hardest yes- and no-instances produced by the evolutionary algorithms. Results show that the hardest no-instance resides on top of a steep cliff, while the hardest yes-instance turns out to be part of a plateau of 27 equally hard instances. While definitive answers are far away, the results provide a lot of insight in the Hamiltonian cycle problem’s state space.

Original languageEnglish
Article number372
Pages (from-to)1-16
Number of pages16
JournalSN Computer Science
Volume3
Issue number5
Early online date15 Jul 2022
DOIs
Publication statusPublished - Sept 2022

Bibliographical note

Funding Information:
ECTA’s reviewers really made an effort to understand and thoroughly annotate the predecessor of this paper which led to this extended version. For the journal paper, two reviewers of Springer Nature Computer Science did an excellent job by not only reading, but recalculating, interpreting and discussing our findings. Thank you all, for adding your fruits of thought to our pie.

Publisher Copyright:
© 2022, The Author(s).

Keywords

  • Evolutionary algorithms
  • Hamiltonian cycle problem
  • Instance hardness
  • NP-complete
  • Plant propagation algorithm

Fingerprint

Dive into the research topics of 'The Hardest Hamiltonian Cycle Problem Instances: The Plateau of Yes and the Cliff of No'. Together they form a unique fingerprint.

Cite this