Deciding Graph non-Hamiltonicity via a Closure Algorithm

Abstract

We present a matching and LP based heuristic algorithm that decides graph non-Hamiltonicity. Each of the <em>n</em>! Hamilton cycles in a complete directed graph on <em>n</em> + 1 vertices corresponds with each of the <em>n</em>! <em>n</em>-permutation matrices <em>P</em>, such that <em>p_u</em>_,<em>i</em> = 1 if and only if the <em>i^th</em> arc in a cycle enters vertex <em>u</em>, starting and ending at vertex <em>n</em> + 1. A graph instance (<em>G</em>) is initially coded as exclusion set <em>E</em>, whose members are pairs of components of <em>P</em>, {<em>p</em>_{<em>u</em>,<em>i</em>}, <em>p_v</em>_{,<em>i</em>+1}}, <em>i</em> = 1, <em>n</em> - 1, for each arc (<em>u</em>, <em>v</em>) not in