Counting perfect matchings and Hamiltonian cycles faster

Abstract

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 number of Hamiltonian cycles of an $n$-vertex directed graph can be computed in time $2^{n-\Omega (\sqrt{n})}$, improving and generalizing an earlier algorithm of Björklund, Kaski, and Williams (Algorithmica 2019) that runs in time $2^{n-\Omega \left(\sqrt{n/\log \log n}\right)}$. A key tool of our approach is the design of a data structure that supports fast evaluation of high-order derivatives of hafnian and Hamiltonian cycles, which integrates with the new approach on multivariate multipoint evaluation by Bhargava, Ghosh, Guo, Kumar, and Umans (FOCS 2022, JACM 2024).

arXiv comment15 pages, to appear in ICALP 2026