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.

我们提出了一种基于变异算法的方法，用于在 Hamilton 图中找到 Hamilton 循环。该方法基于解决非对称旅行推销员问题的已有方法，通过引入更强大的局部搜索进行优化。我们的方法还引入了一种策略，对所考虑的 Hamilton 图进行稀疏化处理，并在搜索过程中进行动态增加。这种综合的启发式方法有助于在较短时间内找到 Hamilton 循环以证明 Hamiltonicity。此外，我们还使用了最近提出的从 Hamilton 循环到对称旅行推销员问题的多项式时间归约方法，基于计算图的传递闭包。尽管我们的方法是元启发式算法，即不能给出找到 Hamilton 循环的理论保证，但我们观察到该方法在实践中成功验证了 Flinder 大学 Hamilton 循环问题挑战集（FHCPSC）中更多实例的 Hamiltonicity，即使对于具有大树宽的图形也是如此。在 FHCPSC 实例上的实验证明以及与最近的五种最先进的基准方法的计算比较表明，所提出的方法在 FHCPSC 的大多数实例中优于其他方法。