Computer Science – Data Structures and Algorithms
Scientific paper
2011-07-13
Computer Science
Data Structures and Algorithms
It has been pointed to us independently by Yuval Peres, Jonah Sherman, Piyush Srivastava and other anonymous reviewers that th
Scientific paper
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(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 algorithm 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. 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.
Jindal Anant
Kochar Gazal
Pal Manjish
No associations
LandOfFree
Maximum Matchings via Glauber Dynamics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Maximum Matchings via Glauber Dynamics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum Matchings via Glauber Dynamics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-165279