Code, Datasets, and Results for: Improving Backtracking for the Hamiltonian Cycle Problem

Contains the source code, problem instances, and results for the paper. The paper evaluates Tambourine, a novel backtracking algorithm for the HCP with the Jingle non-Hamiltonicity check against a backtracker by Vandegriend and Culberson algorithm (Vacul). The evaluation covers 7,198,292 randomly generated graph instances (V = 24, 32, 40, 48), the wall-and-clique instances, 105 optical network topologies of Topology Bench, and 260 instances derived from three infrastructure networks. Naming note: the identifiers in file names and result files predate the paper's final naming. vacul and vandegriend both denote the algorithm the paper calls Vacul, jingle denotes the algorithm the paper calls Tambourine. The instance files use a bespoke binary encoding, that is read by GraphReader.scala in code.zip. The result files are plain JSON, one record per instance, with the fields id, size (number of vertices), degree (average degree), hamiltonian (true/false, or null if the cutoff was reached), iterations (recursions used), nanoseconds (wall-clock time), algorithm, and path (a Hamiltonian cycle if one was found). Files: - code.zip: source code: the solvers, instance generation, and experiment code.- instances-topology-bench.zip: the 105 Topology Bench networks converted to the paper's format. Source data: Topology Bench (doi:10.5281/zenodo.13921775).- results-topology-bench.zip: per-network results on the Topology Bench networks.- instances-random.zip: the randomly generated instances: 24.bin, 32.bin, 40.bin, 48.bin.- instances-wallclique.zip: wall-and-clique instances for V = 8-14, 24, 32, 40, 48, 332, 1174, 2939.- instances-infrastructure.zip: 260 instances obtained by densifying three infrastructure networks: USAir97 (V = 332, 60 instances), euroroad (V = 1174, 120 instances), openflights (V = 2939, 80 instances).- results-infrastructure.zip: per-instance results on the densified infrastructure instances.- results-random.zip: per-instance results on the random instances: result-vacul-<V>.json, result-jingle-<V>.json, result-rubin-<V>.json.- results-wallclique.zip: per-size results of the vandegriend, jingle, and rubin runs on the wall-and-clique instances. Random instance set sizes: - V = 24: 1,199,964 instances- V = 32: 1,599,843 instances- V = 40: 1,999,360 instances- V = 48: 2,399,125 instances