DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.138

Counting Perfect Matchings and Hamiltonian Cycles Faster

Authors: Baitian Li

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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).

Cite as

Baitian Li. Counting Perfect Matchings and Hamiltonian Cycles Faster. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 138:1-138:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{li:LIPIcs.ICALP.2026.138,
  author =	{Li, Baitian},
  title =	{{Counting Perfect Matchings and Hamiltonian Cycles Faster}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{138:1--138:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.138},
  URN =		{urn:nbn:de:0030-drops-265278},
  doi =		{10.4230/LIPIcs.ICALP.2026.138},
  annote =	{Keywords: permanent, hafnian, Hamiltonian cycle, Kakeya sets}
}

Search Results

Documents authored by Li, Baitian

Counting Perfect Matchings and Hamiltonian Cycles Faster

Abstract

Cite as

Thanks for your feedback!

Could not send message