Counting k-Matchings of Bipartite Graphs

A parameterized distribution is defined on the set of all matchings, such that it asymptotically converges to a uniform distribution over maximum matchings. This distribution can be approximated using Bethe Approximation and Loopy Annealing Belief Propagation to extract the matching number. This method can also be used to compute the lower bound on the number of k-matchings of a bipartite graph. Furthermore, the bounds are tight for a sequence of random 2-lifts of the original graph. If the graph is weighted, then a similar approach can be used to get the lower bounds on permanent and sub-permanent sums. We conducted basic experiments to check efficiency of MPA to approximate permanents of various ensembles of sparse matrices.

I have been meaning to write a report about this. Meanwhile, you can find the collection of papers I read (which are digitally annotated in awful handwriting) here.