patternModerate
Sampling perfect matching uniformly at random
Viewed 0 times
randomuniformlysamplingperfectmatching
Problem
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?
Solution
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.
Both these papers uses rapidly mixing Markov chains, and so the samples are only almost uniform. I imagine that uniform sampling is difficult.
Context
StackExchange Computer Science Q#10756, answer score: 10
Revisions (0)
No revisions yet.