Home // International Journal On Advances in Intelligent Systems, volume 14, numbers 1 and 2, 2021 // View article

Backtracking (the) Algorithms on the Hamiltonian Cycle Problem

Authors:
Joeri Sleegers
Daan van den Berg

Keywords: Hamiltonian Cycle; exact algorithm; exhaustive algorithm; heuristic; phase transition; order parameter; data analytics; instance hardness; replication

Abstract:
Even though the Hamiltonian cycle problem is NPcomplete, many of its problem instances are not. In fact, almost all the hard instances reside in one area: near the Komlos- ´ Szemeredi bound, where randomly generated graphs have an ´ approximate 50% chance of being Hamiltonian. If the number of edges is either much higher or much lower, the problem is not hard – most backtracking algorithms decide such instances in (near) polynomial time. Recently however, targeted search efforts have identifed very hard Hamiltonian cycle problem instances very far away from the Komlos-Szemer ´ edi bound. In that study, ´ the used backtracking algorithm was Vandegriend-Culberson’s, which was supposedly the most effcient of all Hamiltonian backtracking algorithms. In this paper, we make a unifed large scale quantitative comparison for the best known backtracking algorithms described between 1877 and 2016. We confrm the suspicion that the Komlos-Szemer ´ edi bound is a hard area for all ´ backtracking algorithms, but also that Vandegriend-Culberson is indeed the most effcient algorithm, when expressed in consumed computing time. When measured in recursive effectiveness however, the algorithm by Frank Rubin, almost half a century old, performs best. In a more general algorithmic assessment, we conjecture that edge pruning and non-Hamiltonicity checks might be largely responsible for these recursive savings. When expressed in system time however, denser problem instances require much more time per recursion. This is most likely due to the costliness of the extra search pruning procedures, which are relatively elaborate. We supply large amounts of experimental data, and a unifed single-program implementation for all six algorithms. All data and algorithmic source code is made public for further use by our colleagues.

Pages: 1 to 13

Copyright: Copyright (c) to authors, 2021. Used with permission.

Publication date: December 31, 2021

Published in: journal

ISSN: 1942-2679