Maximum Matchings via Glauber Dynamics

In this paper we study the classic problem of computing a maximum cardinality matching in general graphs G=(V,E). The best known algorithm for this problem till date runs in O(mn?) time due to Micali and Vazirani \cite{MV80}. Even for general bipartite graphs this is the best known running time (the algorithm of Karp and Hopcroft \cite{HK73} also achieves this bound). For regular bipartite graphs one can achieve an O(m) time algorithm which, following a series of papers, has been recently improved to O(nlogn) by Goel, Kapralov and Khanna (STOC 2010) \cite{GKK10}. In this paper we present a randomized algorithm based on the Markov Chain Monte Carlo paradigm which runs in O(mlog2n) time, thereby obtaining a significant improvement over \cite{MV80}.
We use a Markov chain similar to the \emph{hard-core model} for Glauber Dynamics with \emph{fugacity} parameter ?, which is used to sample independent sets in a graph from the Gibbs Distribution \cite{V99}, to design a faster algorithm for finding maximum matchings in general graphs. Our result crucially relies on the fact that the mixing time of our Markov Chain is independent of ?, a significant deviation from the recent series of works \cite{GGSVY11,MWW09, RSVVY10, S10, W06} which achieve computational transition (for estimating the partition function) on a threshold value of ?. As a result we are able to design a randomized algorithm which runs in O(mlog2n) time that provides a major improvement over the running time of the algorithm due to Micali and Vazirani. Using the conductance bound, we also prove that mixing takes ?(mk) time where k is the size of the maximum matching.