A heuristics approach to Hamiltonian completion problem (HCP)

The Hamiltonian completion problem is an NP-hard problem which consists of finding the smallest number of additional edges to make the graph Hamiltonian. This minimal number of extra edges is defined to be the Hamiltonian Completion Number (HCN). This is a well known problem but rarely analyzed in academic circles. We study the problem on random sparse graphs and compare results of determining HCN with different heuristic approaches. We developed a modification of the Ant colony optimization (ACO) and show that, while the standard ACO presents a better approach to this problem than observed Genetic and Immunological algorithms, the modified ACO provides the best results by far.