Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2309.15422 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915972813684736 |
|---|---|
| author | Li, Baitian |
| author_facet | Li, Baitian |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_15422 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Counting perfect matchings and Hamiltonian cycles faster Li, Baitian Data Structures and Algorithms 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). |
| title | Counting perfect matchings and Hamiltonian cycles faster |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2309.15422 |