Counting perfect matchings and Hamiltonian cycles faster

Baitian Li

We show that the hafnian of a symmetric $2n\times 2n$ matrix of $\mathrm{poly}(n)$-bit integers (which counts the number of perfect matchings of a $2n$-vertex graph) and the…