A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915096391843840 |
|---|---|
| author | Izumi, Taisuke Kitamura, Naoki Yamaguchi, Yutaro |
| author_facet | Izumi, Taisuke Kitamura, Naoki Yamaguchi, Yutaro |
| contents | In this paper, we propose a randomized $\tilde{O}(μ(G))$-round algorithm for the maximum cardinality matching problem in the CONGEST model, where $μ(G)$ means the maximum size of a matching of the input graph $G$. The proposed algorithm substantially improves the current best worst-case running time. The key technical ingredient is a new randomized algorithm of finding an augmenting path of length $\ell$ with high probability within $\tilde{O}(\ell)$ rounds, which positively settles an open problem left in the prior work by Ahmadi and Kuhn [DISC'20].
The idea of our augmenting path algorithm is based on a recent result by Kitamura and Izumi [IEICE Trans.'22], which efficiently identifies a sparse substructure of the input graph containing an augmenting path, following a new concept called \emph{alternating base trees}. Their algorithm, however, resorts in part to a centralized approach of collecting the entire information of the substructure into a single vertex for constructing a long augmenting path. The technical highlight of this paper is to provide a fully-decentralized counterpart of such a centralized method. To develop the algorithm, we prove several new structural properties of alternating base trees, which are of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_04140 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching Izumi, Taisuke Kitamura, Naoki Yamaguchi, Yutaro Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Combinatorics In this paper, we propose a randomized $\tilde{O}(μ(G))$-round algorithm for the maximum cardinality matching problem in the CONGEST model, where $μ(G)$ means the maximum size of a matching of the input graph $G$. The proposed algorithm substantially improves the current best worst-case running time. The key technical ingredient is a new randomized algorithm of finding an augmenting path of length $\ell$ with high probability within $\tilde{O}(\ell)$ rounds, which positively settles an open problem left in the prior work by Ahmadi and Kuhn [DISC'20]. The idea of our augmenting path algorithm is based on a recent result by Kitamura and Izumi [IEICE Trans.'22], which efficiently identifies a sparse substructure of the input graph containing an augmenting path, following a new concept called \emph{alternating base trees}. Their algorithm, however, resorts in part to a centralized approach of collecting the entire information of the substructure into a single vertex for constructing a long augmenting path. The technical highlight of this paper is to provide a fully-decentralized counterpart of such a centralized method. To develop the algorithm, we prove several new structural properties of alternating base trees, which are of independent interest. |
| title | A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2311.04140 |