Exact Sampling from Perfect Matchings of Dense Nearly Regular Bipartite Graphs

Simple item page
dc.creatorHuber, Mark
dc.date2003-10-05
dc.date.accessioned2026-07-07T05:01:38Z
dc.date.available2026-07-07T05:01:38Z
dc.descriptionWe 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 $Θ(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 $γ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^{4.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.
dc.identifierhttps://arxiv.org/abs/math/0310059
dc.identifierhttp://arxiv.org/abs/math/0310059
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/68747
dc.subjectProbability
dc.subject65C05 (Primary); 65C50 (Secondary)
dc.titleExact Sampling from Perfect Matchings of Dense Nearly Regular Bipartite Graphs
dc.typetext

Files

Collections

arXiv