2026-09-08T02:22:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26527 2026-09-05T19:46:34Z ddc:004 open_access

Counting Perfect Matchings and Hamiltonian Cycles Faster Li, Baitian permanent hafnian Hamiltonian cycle Kakeya sets We show that the hafnian of a symmetric 2n× 2n matrix of 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-Ω(√n)}, improving and generalizing an earlier algorithm of Björklund, Kaski, and Williams (Algorithmica 2019) that runs in time 2^{n - Ω(√{n/log log n})}. 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Baitian Li 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.138 urn:nbn:de:0030-drops-265278 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.138 eng https://creativecommons.org/licenses/by/4.0/legalcode