A Memetic Algorithm To Find a Hamiltonian Cycle in a Hamiltonian Graph
This work addresses the Hamiltonian cycle problem for computational graph theory, offering a practical metaheuristic that improves performance on challenging instances, though it is incremental as it builds on existing methods.
The paper tackles the problem of finding Hamiltonian cycles in Hamiltonian graphs by proposing a memetic algorithm that combines local search enhancements and dynamic graph sparsification, resulting in faster verification of Hamiltonicity and outperforming five state-of-the-art baselines on most instances from the Flinder University Hamiltonian Cycle Problem Challenge Set.
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 \textit{Flinder 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.