Perfect
Matchings in O(n^{1.5}) Time in Regular Bipartite
Graphs
By

Prof.
Sanjeev Khanna

Professor of Computer
and Information Science,University of Pennsylvania







Date:
July 29, 2009 (Wednesday) 
Time:
2:30p.m.  3:30 p.m. 
Venue:
Rm. 121, Ho Sin Hang Engineering Building, CUHK 
Abstract
:
We consider the wellstudied problem of finding a
perfect matching in $d$regular bipartite graphs with
$2n$ vertices and $m = nd$ edges. While the bestknown
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 twostage 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 HopcroftKarp 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. 