  We present the first algorithm for generating random variates exactly
uniformly from the set of perfect matchings of a bipartite graph with a
polynomial expected running time over a nontrivial set of graphs. Previous
Markov chain approaches obtain approximately uniform variates for arbitrary
graphs in polynomial time, but their general running time is $\Theta(n^{26}
(\ln n)^2).$ Our algorithm employs acceptance/rejection together with a new
upper limit on the permanent of a form similar to Bregman's Theorem. For a
graph with $2n$ nodes where the degree of every node is nearly $\gamma n$ for a
constant $\gamma$, the expected running time is $O(n^{1.5 + .5/\gamma})$. Under
these conditions, Jerrum and Sinclair showed that a Markov chain of Broder can
generate approximately uniform variates in $\Theta(n^{4.5 + .5/\gamma} \ln n)$
time, making our algorithm significantly faster on this class of graph. With
our approach, approximately counting the number of perfect matchings
(equivalent to finding the permanent of a 0-1 matrix and so $\sharp P$
complete) can be done without use of selfreducibility.
