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

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 $O(\min \{m,\frac{n^{2.5}\ln n}{d}\})$ expected time, an expression that is bounded by $\tilde{O}(n^{1.75})$. In this paper, we further improve this result by giving an $O(\min \{m,\frac{n^2{\ln }^{3}n}{d}\})$ expected time algorithm for finding a perfect matching in regular bipartite graphs; as a function of $n$ alone, the algorithm takes expected time $O((n\ln n{)}^{1.5})$. To obtain this result, we design and analyze a two-stage sampling scheme that reduces the problem of finding a perfect matching in a regular bipartite graph to the same problem on a subsampled bipartite graph with $O(n\ln n)$ edges that has a perfect matching with high probability. The matching is then recovered using the Hopcroft-Karp algorithm. While the standard analysis of Hopcroft-Karp gives us an $\tilde{O}(n^{1.5})$ running time, we present a tighter analysis for our special case that results in the stronger $\tilde{O}(\min \{m,\frac{n^2}{d}\})$ time mentioned earlier. Our proof of correctness of this sampling scheme uses a new correspondence theorem between cuts and Hall's theorem ``witnesses'' for a perfect matching in a bipartite graph that we prove. We believe this theorem may be of independent interest; as another example application, we show that a perfect matching in the support of an $n\times n$ doubly stochastic matrix with $m$ non-zero entries can be found in expected time $\tilde{O}(m+n^{1.5})$.

Added analysis of the Hopcroft-Karp algorithm on the subsampled graph