Exact sampling from perfect matchings of dense regular bipartite graphs

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 results obtain approximately uniform variates for arbitrary graphs in polynomial time, but their general running time is Theta(n(10)(1n n)(2)). Other algorithms (such as Kasteleyn's O(n(3)) algorithm for planar graphs) concentrated on restricted versions of the problem. Our algorithm employs acceptance/rejection together with a new upper limit on the permanent of a form similar to Bregman's theorem. For graphs with 2n nodes, where the degree of every node is. n for a constant., 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) 1n n) time, making our algorithm significantly faster on this class of graphs. The problem of counting the number of perfect matchings in these types of graphs is #P complete. In addition, we give a 1 + sigma approximation algorithm for finding the permanent of 0-1 matrices with identical row and column sums that runs in O(n(1.5+.5/gamma)(1/sigma(2)) log(1/delta)), where the probability that the output is within 1 + s of the permanent is at least 1 - delta.