In this paper we study the classic problem of computing a maximum cardinality matching in general graphs $G = (V, E)$. This problem has been studied extensively more than four decades. The best known algorithm for this problem till date runs in $O(m \sqrt{n})$ 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 which, following a series of papers, has been recently improved to $O(n \log n)$ 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(m \log^2 n)$ 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 $\lambda$, 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. Motivated by results which show that in the hard-core model one can prove fast mixing times (for e.g. it is known that
for $\lambda$ less than a critical threshold the mixing time of the hard-core model is $O(n \log n)$ \cite{MSW04}, we define an analogous Markov chain (depending upon a parameter $\lambda$)
on the space of all possible partial matchings of a given graph $G$, for which the probability
of a particular matching $M$ in the stationary follows the Gibbs distribution
which is:
\[
\displaystyle \pi(M) = \frac{\lambda^{|M|}}{ \sum_{x \in \Omega} \lambda^{|x|} }
\]
where $\Omega$ is the set of all possible matchings in $G$. \\
We prove upper and lower bounds on the mixing time of this Markov chain. Although our Markov chain is essentially a simple modification of the one used for sampling independent sets from the Gibbs distribution, their properties are quite different. Our result crucially relies on the fact that the mixing time of our Markov Chain is independent of $\lambda$, 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 $\lambda$. As a result we are able to design a randomized algorithm which runs in $O(m\log^2 n)$ 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
$\Omega(\frac{m}{k})$ time where $k$ is
the size of the maximum matching.
In this paper we study the classic problem of computing a maximum cardinality matching in general graphs $G = (V, E)$. This problem has been studied extensively more than four decades. The best known algorithm for this problem till date runs in $O(m \sqrt{n})$ 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 which, following a series of papers, has been recently improved to $O(n \log n)$ 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(m \log^2 n)$ 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 $\lambda$, 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. Motivated by results which show that in the hard-core model one can prove fast mixing times (for e.g. it is known that
for $\lambda$ less than a critical threshold the mixing time of the hard-core model is $O(n \log n)$ \cite{MSW04}, we define an analogous Markov chain (depending upon a parameter $\lambda$)
on the space of all possible partial matchings of a given graph $G$, for which the probability
of a particular matching $M$ in the stationary follows the Gibbs distribution
which is:
\[
\displaystyle \pi(M) = \frac{\lambda^{|M|}}{ \sum_{x \in \Omega} \lambda^{|x|} }
\]
where $\Omega$ is the set of all possible matchings in $G$. \\
We prove upper and lower bounds on the mixing time of this Markov chain. Although our Markov chain is essentially a simple modification of the one used for sampling independent sets from the Gibbs distribution, their properties are quite different. Our result crucially relies on the fact that the mixing time of our Markov Chain is independent of $\lambda$, 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 $\lambda$. As a result we are able to design a randomized algorithm which runs in $O(m\log^2 n)$ 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
$\Omega(\frac{m}{k})$ time where $k$ is
the size of the maximum matching.
It has been pointed to us independently by Yuval Peres, Jonah Sherman, Piyush
Srivastava and other anonymous reviewers that the coupling used in this paper doesn't have
the right marginals because of which the mixing time bound doesn't hold, and also the main
result presented in the paper. We thank them for reading the paper with interest and promptly pointing out this mistake.
