4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Dec 16, 2016 at 23:50
  • $\begingroup$ In case your question was motivated by this, see math.stackexchange.com/questions/2050039/…. $\endgroup$
    – domotorp
    Dec 17, 2016 at 10:02
  • $\begingroup$ The case of stable matchings can be interesting $\endgroup$
    – ricardorr
    Dec 18, 2016 at 1:04

2 Answers 2

Reset to default
4
$\begingroup$

The Jerrum-Sinclair-Vigoda algorithm can be used to sample perfect matchings approximately in bipartite graphs. For general graphs, as far as I know, sampling perfect matchings (approximately or exactly) is still open.

Improve this answer
$\endgroup$
4
$\begingroup$

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$.

  1. Huber, Mark. Exact sampling from perfect matchings of dense regular bipartite graphs. Algorithmica 44.3 (2006): 183-193.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.