A report on the results of the ongoing investigation of the Weak Closure Algorithm (WCA)

Adrian Lee, University of Guelph

The non-Hamiltonian cycle decision problem is co-NP complete for which the existence of a polynomial time algorithm is unknown. In 2017, Gismondi and Lee developed a heuristic algorithm (O(n8)) called the weak closure algorithm (WCA) that investigated this problem using a total of 461 snarks that are known to be non-Hamiltonian. This algorithm successfully decided these snarks to be non-Hamiltonian. In this presentation, a follow up report of an ongoing investigation of the WCA testing a total of 459,986 3-regular graphs with vertex counts ranging from 4 to 18; and also 153,000 out of 510,489 3-regular graphs with 20 vertices is presented. All non-Hamiltonian graphs were verified non-Hamiltonian, and, no Hamiltonian graph was decided non-Hamiltonian (Hamiltonian graphs cause the WCA to exit Undecided) via Maple 2023. All tested graphs were generated by GENREG, an open-source software developed by Meringer in 1999.