Papers Published
Abstract:
e 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 running time is Θ(n^10 (ln n)^2). Other algorithms (such as Kasteleyn's O(n^3) 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(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 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 sumns that runs in &O(n^{1.5 + .5/γ} (1 / σ^2) ln (1 / σ)) time, where the probability that the output is within 1 + σ of the permanent is at least 1 - &delta.