Mathematics – Probability
Scientific paper
2003-10-05
Mathematics
Probability
Scientific paper
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 $\Theta(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 $\gamma n$ for a constant $\gamma$, 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} \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.
No associations
LandOfFree
Exact Sampling from Perfect Matchings of Dense Nearly Regular Bipartite Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Exact Sampling from Perfect Matchings of Dense Nearly Regular Bipartite Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact Sampling from Perfect Matchings of Dense Nearly Regular Bipartite Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-652403