# Fast Hamiltonicity checking via bases of perfect matchings

For an even integer t \geq 2, the Matchings Connecivity matrix H t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph K t on t vertices; an entry H tM 1,M 2 is 1 if M 1\cup M 2 is a Hamiltonian cycle and 0 otherwise. Motivated by the computational study of the Hamiltonicity problem, we present three results on the structure of H t: We first show that H t has rank at most 2^{t-2-1} over GF(2) via an appropriate factorization that explicitly provides families of matchings X t forming bases for H t. Second, we show how to quickly change representation between such bases. Third, we notice that the sets of matchings X t induce permutation matrices within H t. Subsequently, we use the factorization to obtain an 1.888^n n^{O(1)} time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Our algorithm as well counts the number of Hamiltonian cycles modulo two in directed bipartite or undirected graphs in the same time bound. Moreover, we use the fast basis change algorithm from the second result to present a Monte Carlo algorithm that given an undirected graph on n vertices along with a path decomposition of width at most pw decides Hamiltonicity in (2+\sqrt{2})^{pw}n^{O(1)} time. Finally, we use the third result to show that for every \epsilon >0 this cannot be improved to (2+\sqrt{2}-\epsilon)^{pw}n^{O(1)} time unless the Strong Exponential Time Hypothesis fails, i.e., a faster algorithm for this problem would imply the breakthrough result of a (2-\epsilon)^n time algorithm for CNF-Sat.

Author: Marek Cygan; Stefan Kratsch; Jesper Nederlof

Source: https://archive.org/