Approximately Counting Perfect and General Matchings in Bipartite and General Graphs

Abstract

We develop algorithms to approximately count perfect matchings in bipartite graphs (or permanents of the corresponding adjacency matrices), perfect matchings in nonbipartite graphs (or hafnians), and general matchings in bipartite and nonbipartite graphs (or matching generating polynomials). First, we study the problem of approximating the permanent and generating weighted perfect matchings in bipartite graphs from their correct distribution. We present a perfect sampling algorithm using self-reducible acceptance/rejection and an upper bound for the permanent. It has a polynomial expected running time for a class of dense problems, and it gives an improvement in running time by a factor of $n^3$ for matrices that are (.6)-dense. Next, we apply the similar approach to study perfect matchings in nonbipartite graphs and also general matchings in general graphs. Our algorithms here have a subexponential expected running time for some classes of nontrivial graphs and are competitive with other Markov chain Monte Carlo methods.