  This manuscript discusses computation of the Partition Function (PF) and the
Minimum Weight Perfect Matching (MWPM) on arbitrary, non-bipartite graphs. We
present two novel problem formulations - one for computing the PF of a Perfect
Matching (PM) and one for finding MWPMs - that build upon the inter-related
Bethe Free Energy, Belief Propagation (BP), Loop Calculus (LC), Integer Linear
Programming (ILP) and Linear Programming (LP) frameworks. First, we describe an
extension of the LC framework to the PM problem. The resulting formulas, coined
(fractional) Bootstrap-BP, express the PF of the original model via the BFE of
an alternative PM problem. We then study the zero-temperature version of this
Bootstrap-BP formula for approximately solving the MWPM problem. We do so by
leveraging the Bootstrap-BP formula to construct a sequence of MWPM problems,
where each new problem in the sequence is formed by contracting odd-sized
cycles (or blossoms) from the previous problem. This Bootstrap-and-Contract
procedure converges reliably and generates an empirically tight upper bound for
the MWPM. We conclude by discussing the relationship between our iterative
procedure and the famous Blossom Algorithm of Edmonds '65 and demonstrate the
performance of the Bootstrap-and-Contract approach on a variety of weighted PM
problems.
