Complexity of Uniform Generation of Perfect Matchings
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$. 


Huber, Mark. Exact sampling from perfect matchings of dense regular bipartite graphs. Algorithmica 44.3 (2006): 183-193.