Investigating the Use of Perfecting Matching in an Algorithm to Detect Non-Hamiltonicity of Snarks

Abstract

The Hamilton cycle decision problem is NP-complete. No polynomial time algorithm that solves this problem is known, and may or may not exist. In this thesis, the co-NP complete non-Hamilton cycle decision problem is investigated via the heuristic O(n^8) weak closure algorithm, with modifications that exploit perfect matching to a greater extent. Hamilton cycles are expressed as specially constructed block permutation matrices. The algorithm attempts to decide a graph's non-Hamiltonicity by checking for the non-existence of these permutation matrices using the bipartite matching algorithm. A small collection of snarks are tested and the algorithm correctly identifies these graphs as non-Hamiltonian.