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?
Sampling perfect matching uniformly at random
algorithms;complexity theory;matching;sampling
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.