# Complexity of Uniform Generation of Perfect Matchings

Jerrum,Valiant and Vazirani on their paper "Random generation of combinatorial structures from a uniform" (http://www.cc.gatech.edu/~vazirani/AppCount.pdf) talk about seeing problems related to relations in a "Existence, Construction, Uniform Generation and Counting" hierarchy.

In the case of the of M being a perfect matching in a bipartite graph G, we know that the problems of existence and construction are easy, and the counting problem is #P-Complete. The uniform generation problem is to generate a perfect matching in such a way that all perfect matching have the same probability

¿Is anything know about the problem of uniform generation of perfect matchings?

• There is a famous FPRAS for the number of perfect matchings which uses approximately uniform sampling from the set of perfect matchings: cc.gatech.edu/~vigoda/Permanent.pdf. I am not sure there is much known about exact uniform sampling. – Sasho Nikolov Dec 16 '16 at 23:50
• In case your question was motivated by this, see math.stackexchange.com/questions/2050039/…. – domotorp Dec 17 '16 at 10:02
• The case of stable matchings can be interesting – ricardorr Dec 18 '16 at 1:04

In [1], the author presents an acceptance/rejection algorithm for generating a uniform sample from the set of perfect matchings of a bipartite graph. While the samples are exactly uniform regardless of the structure of the graph, the run-time is only guaranteed to be polynomial if the graph has a particular structure -- essentially, if the degree of each node is $\gamma n \pm O(log (n))$ for some constant $\gamma$.