Simple deterministic approximation algorithms for counting matchings

We construct a deterministic fully polynomial time approximationscheme (FPTAS) for computing the total number of matchings in abounded degree graph. Additionally, for an arbitrary graph, weconstruct a deterministic algorithm for computing approximately thenumber of matchings within running time exp(O(√n log 2 n)),where n is the number of vertices.

Authors

• Mohsen Bayati
• David Gamarnik
• Dimitriy A. Katz
• Chandra Nair
• Prasad Tetali

Keywords

• matching
• partition function
• correlation decay
• FPTAS