Maximum matching algorithms run faster on regular nonbipartite graphs
Maximum Matching on Regular Nonbipartite Graphs
Data Structures and AlgorithmsDiscrete Mathematics
Summary
Finding the largest possible matching in a network is a way to pair up points without overlap. The authors show that old, classic algorithms run faster than previously thought on networks where each point connects to the same number of others, even if the network structure is complex. This speed boost applies to both kinds of networks that either split into two groups or don’t. Their work means there is no need for new methods to improve matching times in these specific networks.
What this means in practice
- •For network engineers: Compute maximum matchings in regular network topologies more efficiently using existing classic algorithms without new implementations.
- •For data center operators: Optimize resource pairing in systems modeled as regular nonbipartite graphs with guaranteed faster matching computations.
Authors
Varsha Dani, Thomas P. Hayes, Seth Pettie
Abstract
Blocking flow-type maximum matching algorithms are based on finding maximal sets of shortest augmenting paths. They run in $O(m\sqrt{n})$ time, on both bipartite [HK73, Din70, Kar73a, Kar73a] and nonbipartite graphs [GT91, Gab17, Vaz24], but this time bound can be improved if the input is constrained. In this paper we consider $d$-regular bipartite and nonbipartite graphs. Previous algorithms show that a perfect matching in $d$-regular bipartite graphs can be computed in near-linear time deterministically [COS01] or sublinear time with high probability [GKK13]. On $d$-regular non-bipartite graphs, a $(1-1/(d+1))$-approximation can be computed in sublinear time $O(n \log n)$ with high probability [DH25], and hence a maximum matching can be computed in $O(n^2)$ time, w.h.p., which is slightly faster than the best deterministic algorithm for regular graphs [Yus13], running in O(n^2 log n) time. We prove that any blocking flow-type maximum matching algorithm based on finding shortest augmenting paths runs in $O(n^2)$ time on d-regular graphs, both bipartite and nonbipartite. On nonbipartite graphs this is an asymptotic improvement over $O(n^2 \log n)$ [Yus13] and an improvement over $O(m\sqrt{n})$ [GT91, Gab17, Vaz24] when $d = ω(\sqrt{n})$. It also improves [DH25] by making its $O(n^2)$ bound deterministic. However, the main take-away message is that no new algorithms are needed: the "classic" matching algorithms automatically outperform [Yus13, DH25]. We also consider extensions of our results to graphs that are only "nearly regular," meaning that their degrees all lie within a specified range, $[d, Δ]$.