Perfect Matchings in Regular Bipartite Graphs

Sanjeev Khanna
University of Pennsylvania

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 a regular
bipartite graph in time that is sub-linear in the number of edges. 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.

Back to Workshop III: Discrete Optimization