  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.
