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

Ashish Goel, Michael Kapralov, Sanjeev KhannaComb 2019 · DOI

TL;DR

This paper presents a new algorithm that finds perfect matchings in regular bipartite graphs significantly faster than previous methods, achieving an expected time complexity of $\tilde{O}(n^{1.5})$. This is a substantial improvement over existing algorithms, particularly for dense graphs, and relies on a novel "proportionate uncrossing" technique to effectively sample graph edges.

What Problem Does This Paper Address?

Finding a perfect matching in a bipartite graph is a fundamental problem in graph theory with applications in areas like scheduling and resource allocation. For general bipartite graphs, the well-known Hopcroft-Karp algorithm has a time complexity of $O(m\sqrt{n})$, where $m$ is the number of edges and $n$ is the number of vertices. For the specific case of regular bipartite graphs (where every vertex has the same degree $d$), algorithms exist that can achieve $O(m)$ time. However, recent work showed that sampling-based approaches could achieve $\tilde{O}(n^{1.75})$ expected time. This paper aims to push this boundary further, seeking a faster algorithm for regular bipartite graphs, specifically targeting an $\tilde{O}(n^{1.5})$ expected time complexity. The challenge lies in efficiently reducing the problem size through sampling while guaranteeing that a perfect matching is preserved.

Methods

The core of the paper's contribution lies in a novel two-stage sampling scheme and a new theoretical tool called "proportionate uncrossing."

  • Two-Stage Sampling:
    • Stage 1 (Sub-linear Uniform Sampling): The algorithm first performs a uniform sampling of edges to reduce the graph size. This stage is designed to preserve certain structural properties of the original graph, crucial for the subsequent steps.
  • Stage 2 (Non-uniform Sampling): A non-uniform sampling scheme (based on the Benczúr-Karger sampling) is then applied to the reduced graph. This stage aims to produce a graph with $\tilde{O}(n)$ edges while preserving a perfect matching with high probability.
  • Proportionate Uncrossing Theorem: This is the key theoretical innovation. It establishes a correspondence between "witness sets" (related to Hall's condition for matchings) and graph cuts. The theorem shows how to transform a collection of "crossing" witness sets (multiple witness sets mapping to the same cut) into a "half-injective" collection where each witness set corresponds to at most two cuts. This uncrossing is crucial for ensuring that sampling preserves the necessary conditions for a perfect matching.
  • Improved Hopcroft-Karp Analysis: While the algorithm uses the standard Hopcroft-Karp algorithm on the sampled graph, the authors provide a tighter analysis for this specific case, leveraging the structure of the sampled graph to achieve a faster runtime than a naive application of Hopcroft-Karp would suggest.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and analysis for a specific class of graphs (regular bipartite graphs) rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Bridging Sampling and Structural Properties: The paper demonstrates that by carefully designing a sampling process, one can reduce the graph size significantly while preserving not just the existence of a perfect matching, but also crucial structural relationships (like those between witness sets and cuts).
  • The Power of "Proportionate Uncrossing": This novel combinatorial tool is the linchpin. It allows the authors to overcome a barrier in sampling-based approaches by showing how to handle situations where multiple graph structures (witness sets) map to the same "bottleneck" (cut). This is essential for ensuring that sampling preserves the conditions for a perfect matching.
  • Tailored Analysis for Hopcroft-Karp: The authors show that the standard Hopcroft-Karp algorithm, when applied to the specially sampled graph, exhibits better performance than its general bound. This highlights the benefit of understanding the specific structure of the input.
  • Connection to Doubly Stochastic Matrices: The paper shows how their techniques can be applied to find perfect matchings in the support of doubly stochastic matrices, offering a slight improvement in runtime for this related problem.

Key Results

  • Algorithm: An algorithm for finding a perfect matching in $d$-regular bipartite graphs with an expected time complexity of $\tilde{O}(n^{1.5})$.
  • Runtime Improvement: This is a significant speedup compared to previous $\tilde{O}(n^{1.75})$ algorithms, especially for dense graphs where $d$ is large. For sparse graphs, the algorithm achieves $O(m)$ time, matching the best known bounds.
  • Theoretical Contribution: The introduction and proof of the "proportionate uncrossing" theorem, a new combinatorial result with potential applications beyond this specific problem.
  • Application: An $\tilde{O}(m + n^{1.5})$ expected time algorithm for finding a perfect matching in the support of an $n \times n$ doubly stochastic matrix.

Limitations and Future Work

  • Probabilistic Guarantee: The algorithm provides a perfect matching with high probability ($1 - O(1/n)$). While this is standard for randomized algorithms, a deterministic guarantee would be stronger.
  • Constant Factors: The $\tilde{O}$ notation hides constant factors, which can be significant in practice. The paper mentions that larger constants can amplify the success probability.
  • Future Work: The authors suggest that their proportionate uncrossing theorem might have other applications. They also note that their approach could be adapted to yield a Monte Carlo algorithm with a worst-case runtime of $\min\{\tilde{O}(n^{1.5}), O(m)\}$, or a Las Vegas algorithm with an expected runtime of the same bound. The paper also hints at an alternative approach using a modified Benczúr-Karger sampling theorem that might circumvent the need for proportionate uncrossing.

Summary updated

BibTeX
@article{goel2019perfect,
  author = {Ashish Goel and Michael Kapralov and Sanjeev Khanna},
  title = {{Perfect Matchings in Õ (n 1.5) Time in Regular Bipartite Graphs}},
  journal = {Comb.},
  year = {2019},
  doi = {10.1007/s00493-015-2653-6},
}
Figure