Counting perfect matchings and Hamiltonian cycles faster
This work provides a faster exact algorithm for two fundamental counting problems in graph theory, offering a concrete improvement over prior results.
The paper presents an algorithm that computes the hafnian of a symmetric matrix (counting perfect matchings) and the number of Hamiltonian cycles in time $2^{n-Ω(\\sqrt{n})}$, improving the previous best bound of $2^{n - Ω(\\sqrt{n/\\log\\log n})}$.
We show that the hafnian of a symmetric $2n\times 2n$ matrix of $\operatorname{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-Ω(\sqrt{n})}$, improving and generalizing an earlier algorithm of Björklund, Kaski, and Williams (Algorithmica 2019) that runs in time $2^{n - Ω\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).