2003/10/05 by Mark Huber, Huber, Mark
Computer Science · Mathematics · #65C05 (Primary) #65C50 (Secondary) #Bayesian Methods and Mixture Models #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Probability (math.PR) #math.PR #msc:65C05 #msc:65C50
paper · pdf · doi:10.48550/arxiv.math/0310059
arxiv created 2003/10/05 · openalex publication_date 2003/10/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Θ(n26 (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 γ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 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.