<p>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.</p>

CC BY-SA 3.0
2016-12-17T08:19:24.800Z
2016-12-17T08:19:24.800Z
Heng Guo
<p>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$. </p>

<ol>
<li>Huber, Mark. <em><a href="https://arxiv.org/pdf/math/0310059.pdf" rel="nofollow noreferrer">Exact sampling from perfect matchings of dense regular bipartite graphs</a>.</em> Algorithmica 44.3 (2006): 183-193.</li>
</ol>

CC BY-SA 3.0
2016-12-17T00:22:37.360Z
2016-12-17T00:22:37.360Z
mhum
<p>Jerrum,Valiant and Vazirani on their paper "Random generation of combinatorial structures from a uniform" (<a href="http://www.cc.gatech.edu/~vazirani/AppCount.pdf" rel="nofollow noreferrer">http://www.cc.gatech.edu/~vazirani/AppCount.pdf</a>) talk about seeing problems related to relations in a "Existence, Construction, Uniform Generation and Counting" hierarchy.</p>

<p>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</p>

<p>¿Is anything know about the problem of uniform generation of perfect matchings?</p>

CC BY-SA 3.0
2016-12-16T23:50:55.087Z
There is a famous FPRAS for the number of perfect matchings which uses approximately uniform sampling from the set of perfect matchings: http://www.cc.gatech.edu/~vigoda/Permanent.pdf. I am not sure there is much known about exact uniform sampling.
Sasho Nikolov
CC BY-SA 3.0
2016-12-17T10:02:39.290Z
In case your question was motivated by this, see http://math.stackexchange.com/questions/2050039/how-should-teams-be-paired-for-first-round-of-champions-league.
domotorp
CC BY-SA 3.0
2016-12-18T01:04:00.877Z
The case of stable matchings can be interesting
ricardorr
<cc.complexity-theory><reference-request><graph-theory><counting-complexity><matching>
Complexity of Uniform Generation of Perfect Matchings
ricardorr
# Complexity of Uniform Generation of Perfect Matchings

(Asked by: username_0 on 2016-12-16)

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?

**Tags:** cc.complexity-theory, reference-request, graph-theory, counting-complexity, matching

> **Comments:**
> **username_1**: There is a famous FPRAS for the number of perfect matchings which uses approximately uniform sampling from the set of perfect matchings: http://www.cc.gatech.edu/~vigoda/Permanent.pdf. I am not sure there is much known about exact uniform sampling.  
> **username_2**: In case your question was motivated by this, see http://math.stackexchange.com/questions/2050039/how-should-teams-be-paired-for-first-round-of-champions-league.  
> **username_0**: The case of stable matchings can be interesting  

---

## 2 answers

### Answer by username_3 on 2016-12-17. Score: 4 | Accepted answer

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.


---

### Answer by username_4 on 2016-12-17. Score: 4

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](https://arxiv.org/pdf/math/0310059.pdf).* Algorithmica 44.3 (2006): 183-193.


---

