Deciding Graph non-Hamiltonicity via a Closure Algorithm

We present a matching and LP based heuristic algorithm that decides graph non-Hamiltonicity. Each of the n! Hamilton cycles in a complete directed graph on n + 1 vertices corresponds with each of the n! n-permutation matrices P, such that pu;i = 1 if and only if the ith arc in a cycle enters vertex u, starting and ending at vertex n + 1. A graph instance (G) is initially coded as exclusion set E, whose members are pairs of components of P, fpu;i; pv;i+1g; i = 1; n􀀀1, for each arc (u; v) not in in G. Accounting for all arcs not in G, E codes precisely the set of cycles not in G. A doubly stochastic-like O(n4) formulation of the Hamilton cycle decision problem is then constructed. We mEach fpu;i; pv;jg is coded as variable qu;i;v;j such that the set of integer extrema is the set of all permutations.We model G by setting each qu;i;v;j = 0 in correspondence with each fpu;i; pv;jg 2 E such that for non-Hamiltonian G, integer solutions cannot exist. We recognize non-Hamiltonicity by iteratively deducing additional qu;i;v;j that can be set zero and expanding E until the formulation becomes infeasible, in which case we recognize that no integer solutions exists i.e. G is decided non-Hamiltonian. The algorithm rst chooses any fpu;i; pv;jg 62 E and sets qu;i;v;j = 1. As a relaxed LP, if the formulation is infeasible, we deduce qu;i;v;j = 0 and fpu;i; pv;jg can be added to E. Then we choose another fpu;i; pv;jg 62 E and start over. Otherwise, as a subset of matching problems together with a subset of necessary conditions, if qu;i;v;j cannot participate in a match, we deduce qu;i;v;j = 0 and fpu;i; pv;jg can be added E. We again choose another fpu;i; pv;jg 62 E and start over. Otherwise qu;i;v;j is undecided, and we exhaustively test all fpu;i; pv;jg 62 E. If E becomes the set of all fpu;i; pv;jg, G is decided non-Hamiltonian. Otherwise G is undecided. We call this the Weak Closure Algorithm. Only non-Hamiltonian G share this maximal property. Over 100 non-Hamiltonian graphs (10 through 104 vertices) and 2000 randomized 31 vertex non-Hamiltonian graphs are tested and correctly decided non-Hamiltonian. For Hamiltonian G, the complement of E provides information about covers of matchings, perhaps useful in searching for cycles. We also present an example where the WCA fails to deduce any integral value for any qu;i;v;j i.e. G is undecided.