Planar Perfect Matching Counting is as Hard as Determinants

Abstract

In the 1960s, Fisher, Kasteleyn and Temperley designed an ingenious algorithm for computing the partition function of the dimer model, or equivalently, for counting perfect matchings in edge-weighted planar graphs (Philos. Mag. 1961; J. Mathematical Phys. 1963). This FKT algorithm later became the foundation for Valiant's holographic algorithms (FOCS 2004; SIAM J. Comput. 2008), which motivated the study of counting problems under the Holant framework. Combined with an algorithm by Yuster (FOCS 2008), the FKT algorithm allows us to count edge-weighted perfect matchings in planar $n$-vertex graphs with $\tilde{O}(n^{ω/2})$ arithmetic operations, where $ω<2.372$ is the matrix multiplication exponent. We prove a corresponding lower bound: Over algebraic circuits and other sufficiently strong computational models, perfect matchings in edge-weighted $n$-vertex planar graphs $G$ cannot be counted in $O(n^{ω/2-ε})$ arithmetic operations. This confirms the optimality of Yuster's algorithm. Our bound holds even when $G$ is an edge-weighted square grid.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.