Fast accurate approximation for counting perfect matchings in graphs
Fast FPRAS for the Permanent
Data Structures and AlgorithmsDiscrete Mathematics
Summary
Counting perfect matchings in a network, which can be represented as the permanent of a matrix, is a tough computational problem. The authors developed a faster randomized algorithm that approximates this count more efficiently than previous methods. They used ideas from electrical flow and Markov chains to reduce the computation time significantly. Their new approach can handle matrices made of zeros and ones, and also extends to nonnegative matrices.
What this means in practice
- •For network analysts: Estimate the number of perfect matchings in large bipartite networks faster to understand connectivity properties.
- •For quantum computing developers: Compute approximate permanents more efficiently which relate to simulating certain quantum phenomena and boson sampling models.
Authors
Xiaoyu Chen, Heng Guo, Eric Vigoda, Xiongxin Yang
Abstract
We give an FPRAS for the permanent of an $n\times n$ $0/1$ matrix with running time $\widetilde{O}(n^{3.5}\varepsilon^{-2})$. Our algorithm extends to a strongly polynomial FPRAS for arbitrary nonnegative matrices, as in previous works. Jerrum, Sinclair, and Vigoda (2004) gave the first FPRAS for the permanent of a nonnegative matrix. The running time was subsequently improved to $\widetilde{O}(n^7)$ by Bezáková, Štefankovič, Vazirani, and Vigoda (2008), and recently to $\widetilde{O}(n^6)$ by Chen, Vigoda, and Yang (2026). We introduce a multicommodity-flow bound inspired by electrical flows, replacing the usual path-length factor by routing energy. For a boosted version of the classical JSV chain, we prove a relaxation-time bound of $O(n^3\log n)$ and show that stationary trajectories of this length estimate all stationary hole-pattern probabilities, yielding an $\widetilde O(n^5)$-time FPRAS algorithm. Our new hole-weighted slide (HWS) chain improves both bounds to $O(n^2\log n)$, yielding an $\widetilde O(n^4)$-time algorithm. Finally, we obtain the claimed $\widetilde O(n^{3.5})$ running time by using a subset of $\widetilde{O}(\sqrt{n})$ checkpoint temperatures in an iterated sequence of warm-starts to obtain initializations at every temperature.