# Mark Huber Publications

Exact sampling from perfect matchings in dense regular graphs

M. Huber,
Algorithmica, vol. 44 (2006), pp. 183–193.

*Abstract: *
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
*Θ(n ^{10} (ln n)^{2})*.
Other algorithms (such as Kasteleyn's

*O(n*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

^{3})*2n*nodes, where the degree of every node is

*γn*for a constant

*γ*, the expected running time is

*O(n*

^{1.5 + .5/γ}). Under these conditions, Jerrum and Sinclair showed that a Markov chain of Broder can generate approximately uniform variates in

*Θ(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 + σ approximation algorithm for finding the permanent of 0–1 matrices with identical row and column sums that runs in

^{4.5 + .5/γ}ln n)*O(n*

^{1.5 + .5/γ}(1/σ

^{2})

*log*(1/δ)), where the probability that the output is within 1 + σ of the permanent is at least 1 – δ.

*Keywords: *

This site supported by NSF CAREER grant DMS-05-48153. Last update: 04 December 2009. Note: All downloads provided solely for use within the restrictions of the Fair Use Act, and all copyrights remain with their respective owners.