pith. sign in

arxiv: 2309.15422 · v2 · submitted 2023-09-27 · 💻 cs.DS

Counting perfect matchings and Hamiltonian cycles faster

Baitian Li This is my paper

Pith reviewed 2026-05-24 07:10 UTC · model grok-4.3

classification 💻 cs.DS
keywords hafnianperfect matchingsHamiltonian cyclescounting algorithmsdata structurespolynomial derivativesmultipoint evaluationexponential time
0
0 comments X

The pith

Hafnians of 2n×2n matrices and Hamiltonian cycle counts in n-vertex digraphs can be computed in time 2^{n-Ω(√n)}.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes faster algorithms for two classic counting problems in graphs. It shows how to compute the hafnian of a symmetric 2n×2n matrix with poly(n)-bit entries, which directly gives the number of perfect matchings in a 2n-vertex graph, and how to count Hamiltonian cycles in an n-vertex directed graph. Both tasks are solved in time 2^{n-Ω(√n)}, which improves on the previous bound of 2^{n-Ω(√(n/log log n))}. The speedup relies on a new data structure for rapidly evaluating high-order derivatives of the associated polynomials, combined with recent techniques for multivariate multipoint evaluation. These problems sit at the core of exact exponential-time algorithms for many graph problems, so shaving an Ω(√n) factor from the exponent has concrete consequences for what instances become tractable.

Core claim

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 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-cycle polynomials, which integrates with the new approach on multivariate multipoint evaluation by Bhargava et al.

What carries the argument

A data structure that supports fast evaluation of high-order derivatives of hafnian and Hamiltonian-cycle polynomials, integrated with multivariate multipoint evaluation.

If this is right

  • The number of perfect matchings in any 2n-vertex graph can be counted in time 2^{n-Ω(√n)} when edge weights are poly(n)-bit integers.
  • The number of Hamiltonian cycles in any n-vertex directed graph can be counted in time 2^{n-Ω(√n)}.
  • The same time bound applies to the permanent of a related matrix obtained from the hafnian construction.
  • The improvement holds for the full range of n where the prior algorithm applied and removes the extra log log n factor in the exponent.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the derivative data structure can be ported to other multivariate polynomials that encode combinatorial counts, similar √n improvements may apply to additional #P problems.
  • The dependence on recent multipoint evaluation advances indicates that further progress on algebraic techniques could yield still faster counting algorithms for these problems.
  • The approach may extend naturally to counting other cycle structures or matchings in directed or weighted settings beyond the two problems treated here.

Load-bearing premise

The newly designed data structure for fast evaluation of high-order derivatives of the hafnian and Hamiltonian-cycle polynomials integrates correctly with the multivariate multipoint evaluation technique.

What would settle it

Running the algorithm on an explicit family of 2n×2n symmetric matrices with poly(n)-bit entries whose hafnian is known by independent means and observing that the runtime exceeds 2^{n-Ω(√n)} or returns an incorrect count would falsify the claim.

read the original abstract

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-\Omega(\sqrt{n})}$, improving and generalizing an earlier algorithm of Bj\"orklund, 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).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper claims to compute the hafnian of a symmetric 2n×2n matrix with poly(n)-bit integer entries (counting perfect matchings in 2n-vertex graphs) and the number of Hamiltonian cycles in an n-vertex directed graph in time 2^{n−Ω(√n)}. This improves the prior bound of 2^{n−Ω(√n/log log n)} from Björklund, Kaski, and Williams (Algorithmica 2019). The approach introduces a data structure for fast high-order derivative evaluation of the hafnian and Hamiltonian-cycle polynomials and integrates it with the multivariate multipoint evaluation framework of Bhargava et al. (FOCS 2022/JACM 2024).

Significance. If the time bound is correct, the result strengthens the state of the art for two canonical #P-hard counting problems by removing an extra log log n factor from the exponent. The combination of a custom derivative data structure with recent multipoint-evaluation machinery is a technically interesting direction; successful verification would constitute a concrete advance in exact exponential algorithms.

major comments (1)
  1. The claimed Ω(√n) improvement in the exponent rests on the new high-order derivative data structure being integrated with Bhargava et al.’s multipoint evaluation so that derivative queries are answered in time sufficiently sub-quadratic in the number of monomials (∼2^{O(√n)}). The manuscript must supply an explicit end-to-end time analysis showing that no hidden polylog or √log factors in the data-structure construction or query reduction erase the net saving; without this calculation the central claim cannot be verified from the given text.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment and for identifying the need for a fully explicit end-to-end runtime analysis. We address the single major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: The claimed Ω(√n) improvement in the exponent rests on the new high-order derivative data structure being integrated with Bhargava et al.’s multipoint evaluation so that derivative queries are answered in time sufficiently sub-quadratic in the number of monomials (∼2^{O(√n)}). The manuscript must supply an explicit end-to-end time analysis showing that no hidden polylog or √log factors in the data-structure construction or query reduction erase the net saving; without this calculation the central claim cannot be verified from the given text.

    Authors: We agree that an explicit, self-contained end-to-end calculation is necessary for verification. Section 4 of the manuscript already derives the per-query cost of the derivative data structure (O(2^{c√n} n^{-ω(1)}) for a suitable constant c < 1/2) and combines it with the multipoint-evaluation cost from Bhargava et al. (FOCS 2022). However, the global accounting that confirms the polylog and √log factors remain absorbed inside the Ω(√n) term is only sketched. In the revision we will add a dedicated subsection (tentatively 4.4) that (i) bounds the preprocessing time of the data structure, (ii) counts the exact number of derivative queries issued by the multipoint evaluator, and (iii) substitutes the concrete exponents to obtain the overall running time 2^{n - Ω(√n)} with all lower-order terms written out. This will make the saving rigorous and directly verifiable. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external cited techniques

full rationale

The claimed 2^{n-Ω(√n)} runtime is obtained by designing a new data structure for high-order derivative evaluation and integrating it with the independently published multivariate multipoint evaluation framework of Bhargava et al. (FOCS 2022/JACM 2024). This is an algorithmic improvement over the cited Björklund-Kaski-Williams 2019 bound rather than a self-definitional or fitted-input reduction. No load-bearing step reduces by construction to the paper's own inputs or to a self-citation chain; the central exponent improvement is presented as arising from the combination of the new data structure with the external multipoint result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

No free parameters, ad-hoc constants, or new postulated entities are visible in the abstract. The work relies on standard algebraic facts about hafnians as polynomials and on the correctness of the two cited external techniques.

axioms (2)
  • standard math Hafnians and directed cycle-counting polynomials admit well-defined high-order partial derivatives that can be evaluated via a data structure.
    Invoked when the abstract introduces the derivative data structure as the key tool.
  • domain assumption The multivariate multipoint evaluation result of Bhargava et al. applies directly once the derivative values are supplied.
    The abstract states that the new data structure 'integrates with' the 2022 technique.

pith-pipeline@v0.9.0 · 5683 in / 1460 out tokens · 38925 ms · 2026-05-24T07:10:02.890489+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Bax and J

    E. Bax and J. Franklin. A finite-difference sieve to count p aths and cycles by length. Inform. Process. Lett., 60(4):171–176, 1996

    work page 1996

  2. [2]

    Bhargava, S

    V. Bhargava, S. Ghosh, Z. Guo, M. Kumar, and C. Umans. Fast multivariate multipoint evaluation over all finite fields. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer S cience—FOCS 2022, pages 221–232. IEEE Computer Soc., Los Alamitos, CA, [2022] ©2022

    work page 2022

  3. [3]

    Bhargava, S

    V. Bhargava, S. Ghosh, M. Kumar, and C. K. Mohapatra. Fast , algebraic multivariate multipoint evaluation in small characteristic and applications. In STOC ’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 403–415. ACM, New York, [2022] ©2022

    work page 2022

  4. [4]

    Bj¨ orklund

    A. Bj¨ orklund. Below all subsets for some permutational counting problems. In 15th Scandinavian Symposium and Workshops on Algorithm Theory , volume 53 of LIPIcs. Leibniz Int. Proc. Inform. , pages Art. No. 17,

    work page

  5. [5]

    Leibniz-Zent

    Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016 . COMPUTING PERMANENTS AND COUNTING HAMILTONIAN CYCLES F AST ER 9

    work page 2016

  6. [6]

    Bj¨ orklund, T

    A. Bj¨ orklund, T. Husfeldt, and I. Lyckberg. Computing t he permanent modulo a prime power. Inform. Process. Lett., 125:20–25, 2017

    work page 2017

  7. [7]

    Bj¨ orklund, P

    A. Bj¨ orklund, P. Kaski, and R. Williams. Generalized Ka keya sets for polynomial evaluation and faster computation of fermionants. Algorithmica, 81(10):4010–4028, 2019

    work page 2019

  8. [8]

    Bj¨ orklund and R

    A. Bj¨ orklund and R. Williams. Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors. In 46th International Colloquium on Automata, Languages, and Programming, volume 132 of LIPIcs. Leibniz Int. Proc. Inform. , pages Art. No. 25, 14. Schloss Dagstuhl. Leibniz-Zent. Inf orm., Wadern, 2019

    work page 2019

  9. [9]

    H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof. D eterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inform. and Comput. , 243:86–111, 2015

    work page 2015

  10. [10]

    Cygan and M

    M. Cygan and M. Pilipczuk. Faster exponential-time algo rithms in graphs of bounded average degree. Inform. and Comput. , 243:75–85, 2015

    work page 2015

  11. [11]

    F. V. Fomin and D. Kratsch. Exact exponential algorithms. Texts Theor. Comput. Sci., EATCS Ser. Berlin: Springer, 2010

    work page 2010

  12. [12]

    R. M. Karp. Reducibility among combinatorial problems . In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights , N.Y., 1972) , The IBM Research Symposia Series, pages 85–103. Plenum, New York-London, 1972

    work page 1972

  13. [13]

    K. S. Kedlaya and C. Umans. Fast polynomial factorizati on and modular composition. SIAM J. Comput. , 40(6):1767–1802, 2011

    work page 2011

  14. [14]

    D. E. Knuth. The art of computer programming. Vol. 2: Seminumerical algo rithms. Addison-Wesley Pub- lishing Co., Reading, Mass.-London-Don Mills, Ont., 1969

    work page 1969

  15. [15]

    H. J. Ryser. Combinatorial mathematics , volume No. 14 of The Carus Mathematical Monographs . Mathe- matical Association of America, ; distributed by John Wiley and Sons, Inc., New York, 1963

    work page 1963

  16. [16]

    L. G. Valiant. The complexity of computing the permanen t. Theoret. Comput. Sci. , 8(2):189–201, 1979

    work page 1979

  17. [17]

    L. G. Valiant. The complexity of enumeration and reliab ility problems. SIAM J. Comput. , 8(3):410–421, 1979

    work page 1979

  18. [18]

    von zur Gathen and J

    J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, Cambridge, third edition, 2013

    work page 2013