[Solved]: Sampling perfect matching uniformly at random

Problem Detail: 

Suppose I have a graph $G$ with $M(G)$ the (unknown) set of perfect matchings of $G$. Suppose this set is non-empty, then how difficult is it to sample uniformly at random from $M(G)$? What if I am okay with a distribution that is close to uniform, but not quite uniform, then is there an efficient algorithm?

Asked By : Artem Kaznatcheev

Answered By : Yuval Filmus

There is a classical paper of Jerrum and Sinclair (1989) on sampling perfect matchings from dense graphs. Another classical paper of Jerrum, Sinclair and Vigoda (2004; pdf) discusses sampling perfect matchings from bipartite graphs.

Both these papers uses rapidly mixing Markov chains, and so the samples are only almost uniform. I imagine that uniform sampling is difficult.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10756