A Memetic Algorithm To Find a Hamiltonian Cycle in a Hamiltonian Graph
<|reference_start|>A Memetic Algorithm To Find a Hamiltonian Cycle in a Hamiltonian Graph: 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.<|reference_end|>
@article{ali2024a,
    title={A Memetic Algorithm To Find a Hamiltonian Cycle in a Hamiltonian Graph},
    author={Sarwan Ali, Pablo Moscato},
    journal={arXiv preprint arXiv:2403.07886},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.07886},
    primaryClass={cs.NE cs.AI cs.DM}
}