On the random generation and counting of matchings in dense graphs

AbstractIn this work we present a fully randomized approximation scheme for counting the number of perfect matchings in a dense bipartite graphs, that is equivalent to get a fully randomized approximation scheme to the permanent of a dense boolean matrix. We achieve this known solution, through novel extensions in the theory of suitable non-reversible, Markov chains which mix rapidly and have a near-uniform distribution