Metraipolis › archive › dc_196841aa0f07
Maximum Matching on Regular Nonbipartite Graphs — arXiv:2609.14126
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.14126
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T02:15:21.414Z
- SHA-256 of the archived text
8731c907635426ae8d6b74dd569e554963a73847346eefbb887fbf4e3e22bd4f- Stable URL of this page
https://metraipolis.com/documento/dc_196841aa0f07
How to cite
Maximum Matching on Regular Nonbipartite Graphs — arXiv:2609.14126 — arXiv (en), https://arxiv.org/abs/2609.14126 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_196841aa0f07 (Metraipolis archive dc_196841aa0f07, sha256 8731c907635426ae8d6b74dd569e554963a73847346eefbb887fbf4e3e22bd4f)
BibTeX
@misc{dc196841aa0f07,
title = {Maximum Matching on Regular Nonbipartite Graphs — arXiv:2609.14126},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.14126},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_196841aa0f07; sha256 8731c907635426ae8d6b74dd569e554963a73847346eefbb887fbf4e3e22bd4f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14126. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 = \omega(\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, \Delta]$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.14126 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T01:54:07.121Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).