DIMACS Theoretical Computer Science Seminar

Title: Perfect Matchings in Regular Bipartite Graphs

Speaker: Sanjeev Khanna, University of Pennsylvania

Date: Wednesday, March 30, 2011 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


The problem of finding a perfect matching in a regular bipartite graph is a classical problem with applications to edge-colorings, routing, and scheduling, and is closely related to the Birkhoff-von Neumann decomposition of doubly stochastic matrices. A sequence of improvements over the years have culminated in a linear-time algorithm for this problem.

This talk considers the question if a perfect matching can be computed in sub-linear time in a regular bipartite graph. We show that using randomization, one can obtain surprisingly efficient sub-linear time algorithms for this problem. In contrast, we show that no deterministic algorithm can do better than linear time.

This is based on joint work with Ashish Goel and Michael Kapralov at Stanford University.