Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs

Ashish Goel, Michael Kapralov, Sanjeev Khanna

Introduction

Finding a perfect matching in a bipartite graph is a fundamental problem in combinatorial optimization and graph theory. A $d$-regular bipartite graph, where every vertex has the same degree $d$ and the vertex set is partitioned into two equal sets of size $n$, is guaranteed by Hall’s Marriage Theorem to contain at least $d$ edge-disjoint perfect matchings. Despite this guarantee, the computational challenge lies in efficiently identifying even one such matching. For several decades, the most efficient algorithms for this task were bounded by a running time of $O(m)$, where $m = nd$ represents the total number of edges. While $O(m)$ is linear relative to the graph size, it becomes $O(n^2)$ in dense graphs where $d$ approaches $n$. This paper presents a randomized algorithm that breaks the $O(m)$ barrier for dense regular bipartite graphs, achieving a complexity of $O(\min\{m, \frac{n^{2.5} \ln n}{d}\})$.

Problem Statement and Historical Context

The primary objective is to find a perfect matching—a set of $n$ edges such that every vertex in the bipartite graph is incident to exactly one edge in the set. Historically, the Hopcroft-Karp algorithm provided a standard benchmark with a complexity of $O(m\sqrt{n})$. For the specific case of $d$-regular bipartite graphs, specialized techniques eventually reduced this to $O(m)$. However, as graphs become denser, the $O(m)$ complexity scales poorly. The research addressed here seeks to leverage the inherent structure of regular graphs to find matchings more efficiently than by simply traversing every edge.

The Uniform Sampling Approach

The core innovation of this work is a Uniform Sampling Theorem. The authors propose that instead of searching the original dense graph $G$, one can search a significantly sparser subgraph $G'$ created by sampling edges independently with a probability $p$.

The Uniform Sampling Theorem

The authors prove that if edges are sampled with a probability $p = O(\frac{n \ln n}{d^2})$, the resulting subgraph $G'$ will contain a perfect matching with high probability. This result is non-trivial because a random subgraph of a $d$-regular graph is not itself regular, and a naive sampling might easily destroy all perfect matchings if the sampling rate is too low.

Connecting Matchings to Graph Cuts

To prove the validity of this sampling rate, the authors establish a novel connection between Hall’s condition and graph cuts. Hall’s Theorem states that a bipartite graph has a perfect matching if and only if every subset of vertices on one side has at least as many neighbors on the other side. A violation of this condition is represented by a "witness set."

The authors demonstrate a one-to-one correspondence between these witness sets and specific graph cuts. This allows them to apply Karger’s sampling theorem, a seminal result in network reliability that shows random sampling preserves the sizes of all cuts in a graph. By showing that the "matching-related" cuts are preserved, they guarantee that the sampled subgraph $G'$ retains the necessary structure to support a perfect matching.

Graph Decomposition

To handle graphs that might contain small cuts (which are more vulnerable to sampling errors), the authors utilize a graph decomposition technique. They conceptually decompose the graph into vertex-disjoint components that possess high connectivity (large min-cuts). While this decomposition is a theoretical tool used to facilitate the proof rather than a step in the algorithm itself, it is essential for ensuring the sampling theorem holds across all $d$-regular bipartite architectures.

The Algorithm

The resulting randomized algorithm follows a straightforward dual-path logic:

  1. Sparse Case: If the graph degree $d$ is small, the algorithm defaults to the existing $O(m)$ approach.
  2. Dense Case: If the graph is dense (large $d$), the algorithm samples edges with probability $p$ to generate a sparse subgraph $G'$. It then applies the classic Hopcroft-Karp algorithm to $G'$.

Because $G'$ has significantly fewer edges than $G$, the Hopcroft-Karp execution is much faster. Specifically, the number of edges in $G'$ is approximately $mp = nd \cdot \frac{n \ln n}{d^2} = \frac{n^2 \ln n}{d}$.

Key Results and Complexity

The algorithm achieves an expected running time of $O(\min\{m, \frac{n^{2.5} \ln n}{d}\})$.

  • Dense Graph Speedup: In the most extreme case of a complete bipartite graph where $d = n$, the complexity reduces to approximately $O(n^{1.5} \ln n)$. This is a significant improvement over the previous $O(n^2)$ limit.
  • Inverse Relationship with Density: A key insight of this work is that the algorithm's efficiency increases as the graph density increases. The larger the degree $d$, the smaller the fraction of edges required in the sample to guarantee a matching.
  • Optimality: The authors provide a lower bound demonstrating that their sampling rate $p = O(\frac{n \ln n}{d^2})$ is nearly optimal. Any significantly lower sampling rate would likely result in a subgraph that fails to contain a perfect matching.

Conclusion and Future Directions

This research successfully breaks the $O(m)$ bottleneck for finding perfect matchings in regular bipartite graphs by bridging the gap between matching theory and cut-preservation theorems. However, several avenues for future work remain. There exists a small logarithmic gap (a factor of $\ln^2 n$) between the proven upper bound and the theoretical lower bound for the sampling rate. Additionally, while this work focuses on uniform sampling, non-uniform sampling strategies might yield even faster results. Finally, extending these sampling theorems to "near-regular" graphs—where vertex degrees are similar but not identical—remains an open challenge for the field.

Summary updated

BibTeX
@inproceedings{goel2009perfect,
  author = {Ashish Goel and Michael Kapralov and Sanjeev Khanna},
  title = {{Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs}},
  booktitle = {SODA},
  year = {2009},
  doi = {10.1137/1.9781611973068.2},
}
Figure