A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs

We give a fully polynomial randomized approximation scheme (FPRAS) for counting perfect matchings in arbitrary finite simple undirected graphs, resolving the general-graph perfect-matching approximation problem. The algorithm returns zero with certainty when no perfect matching exists. Otherwise, it achieves relative error ε with failure probability at most δ in worst-case bit time polynomial in the input length, ${\epsilon }^{-1}$, and $\log {\delta }^{-1}$.