Fast Algorithms for Perfect Matching 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 also 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. In this talk, we will show that graph sparsification and random walks can be used to obtain surprisingly fast sublinear time algorithms for this problem. Our approach also yields an efficient algorithm for computing the Birkhoff-von-Neumann decomposition of a doubly-stochastic matrix.