Mark Huber Publications

Exact sampling from perfect matchings in dense regular graphs
M. Huber, Algorithmica, vol. 44 (2006), pp. 183193.

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 Θ(n10 (ln n)2). Other algorithms (such as Kasteleyn's O(n3) 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(n1.5 + .5/γ). Under these conditions, Jerrum and Sinclair showed that a Markov chain of Broder can generate approximately uniform variates in Θ(n4.5 + .5/γ ln 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 O(n1.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.