Planar Perfect Matching Counting is as Hard as Determinants
2026-06-02 • Computational Complexity
Computational ComplexityDiscrete MathematicsData Structures and Algorithms
AI summaryⓘ
The authors discuss a famous 1960s algorithm called the FKT algorithm, which counts perfect matchings in planar graphs and has important applications in computing. They explain how a later algorithm by Yuster improves the efficiency to roughly n raised to half the power of matrix multiplication exponent. The authors prove that this efficiency is the best possible, meaning no algorithm can do significantly better in terms of arithmetic operations for counting perfect matchings in planar graphs. Their result even applies to simple grid graphs, confirming Yuster's algorithm is optimal in this setting.
FKT algorithmperfect matchingplanar graphpartition functionedge-weighted graphholographic algorithmsarithmetic operationsmatrix multiplication exponentalgebraic circuitscomputational complexity
Authors
Radu Curticapean, Jiaheng Wang
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.