  This paper proposes a local search algorithm for a specific combinatorial
optimisation problem in graph theory: the Hamiltonian Completion Problem (HCP)
on undirected graphs. In this problem, the objective is to add as few edges as
possible to a given undirected graph in order to obtain a Hamiltonian graph.
This problem has mainly been studied in the context of various specific kinds
of undirected graphs (e.g. trees, unicyclic graphs and series-parallel graphs).
The proposed algorithm, however, concentrates on solving HCP for general
undirected graphs. It can be considered to belong to the category of
matheuristics, because it integrates an exact linear time solution for trees
into a local search algorithm for general graphs. This integration makes use of
the close relation between HCP and the minimum path partition problem, which
makes the algorithm equally useful for solving the latter problem. Furthermore,
a benchmark set of problem instances is constructed for demonstrating the
quality of the proposed algorithm. A comparison with state-of-the-art solvers
indicates that the proposed algorithm is able to achieve high-quality results.
