Abstract :

We consider the well-studied problem of finding a perfect matching in $d$-regular bipartite graphs with $2n$ vertices and $m = nd$ edges. While the best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes $O(m \sqrt{n})$ time, in regular bipartite graphs, a perfect matching is known to be computable in $O(m)$ time. Very recently, the $O(m)$ bound was improved to $\tilde{O}(n^{1.75})$ expected time. We further improve this result by giving an $O(n^{1.5})$ expected time algorithm. Our algorithm is based on a two-stage sampling scheme that reduces the problem of finding a perfect matching in regular bipartite graphs to the same problem on arbitrary bipartite graphs with $O(n\ln n)$ edges. This matching is then recovered using the Hopcroft-Karp algorithm. To prove correctness, we establish an interesting correspondence theorem between cuts and Hall's theorem "witnesses" for a perfect matching in a bipartite graph.

This is joint work with Ashish Goel (Stanford) and Michael Kapralov (Stanford).

Biography :

Sanjeev Khanna is a Professor of Computer and Information Science at University of Pennsylvania. He received his PhD from Stanford University in 1996. His research interests are in algorithms and complexity with a focus on approximation algorithms and hardness of approximation. He is recipient of a Guggenheim Fellowship, a Sloan Fellowship, an IBM Faculty Award, an NSF Career Award, and an Arthur Samuel prize for his dissertation.