# A Memetic Algorithm To Find a Hamiltonian Cycle in a Hamiltonian Graph

arXiv: https://arxiv.org/abs/2403.07886 · HTML: https://mlsanity.com/paper/2403.07886/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 89 references that are in the map.
- First posted on arXiv 1 Feb 2024.

## Builds on (most cited first, 4 of 4)

- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Learning to Optimize Neural Nets](https://mlsanity.com/paper/1703.00441/) (2017)
- [Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation](https://mlsanity.com/paper/1803.00927/) (2018)

## Abstract (arXiv)

We present a memetic algorithm (maa) approach for finding a Hamiltonian cycle in a Hamiltonian graph. The ma is based on a proven approach to the Asymmetric Travelling Salesman Problem (atspp) that, in this contribution, is boosted by the introduction of more powerful local searches. Our approach also introduces a novel technique that sparsifies the input graph under consideration for Hamiltonicity and dynamically augments it during the search. Such a combined heuristic approach helps to prove Hamiltonicity by finding a Hamiltonian cycle in less time. In addition, we also employ a recently introduced polynomial-time reduction from the hamcyc to the Symmetric tsp, which is based on computing the transitive closure of the graph. Although our approach is a metaheuristic, i.e., it does not give a theoretical guarantee for finding a Hamiltonian cycle, we have observed that the method is successful in practice in verifying the Hamiltonicity of a larger number of instances from the textitFlinder University Hamiltonian Cycle Problem Challenge Set (fhcpsc), even for the graphs that have large treewidth. The experiments on the fhcpscc instances and a computational comparison with five recent state-of-the-art baseline approaches show that the proposed method outperforms those for the majority of the instances in the fhcpsc.