Dynamic Approximate Maximum Matching in the Distributed Vertex Partition Model
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914225958420480 |
|---|---|
| author | Robinson, Peter Zhu, Xianbin |
| author_facet | Robinson, Peter Zhu, Xianbin |
| contents | We initiate the study of approximate maximum matching in the vertex partition model, for graphs subject to dynamic changes. We assume that the $n$ vertices of the graph are partitioned among $k$ players, who execute a distributed algorithm and communicate via message passing. An adaptive adversary may perform dynamic updates to the graph topology by inserting or removing edges between the nodes, and the algorithm needs to respond to these changes by adapting the output of the players, with the goal of maintaining an approximate maximum matching. The main performance metric in this setting is the algorithm's update time, which corresponds to the number of rounds required for updating the solution upon an adversarial change. For the standard setting of single-edge insertions and deletions, we give a randomized Las Vegas algorithm with an expected update time of $O( \lceil \frac{\sqrt{m}}{βk} \rceil )$ rounds that maintains a $\frac{2}{3}$-approximate maximum matching that is also maximal, where $m$ is the number of edges in the graph and $β$ is the available link bandwidth. For batch-dynamic updates, where the adversary may insert up to $\ell\ge 1$ edges at once, we prove the following. There is a randomized algorithm that succeeds with high probability in maintaining a $\frac{2}{3}$-approximate maximum matching and has a worst case update time of $O(\lceil\frac{\ell\log n}{\sqrt{βk}}\rceil )$ rounds. Any algorithm for maintaining a maximal matching without 3-augmenting paths under batches of $\ell$-edge insertions has an update time of $Ω( \frac{\ell}{βk \log n} )$ rounds in the worst case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17338 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Dynamic Approximate Maximum Matching in the Distributed Vertex Partition Model Robinson, Peter Zhu, Xianbin Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 68W15 We initiate the study of approximate maximum matching in the vertex partition model, for graphs subject to dynamic changes. We assume that the $n$ vertices of the graph are partitioned among $k$ players, who execute a distributed algorithm and communicate via message passing. An adaptive adversary may perform dynamic updates to the graph topology by inserting or removing edges between the nodes, and the algorithm needs to respond to these changes by adapting the output of the players, with the goal of maintaining an approximate maximum matching. The main performance metric in this setting is the algorithm's update time, which corresponds to the number of rounds required for updating the solution upon an adversarial change. For the standard setting of single-edge insertions and deletions, we give a randomized Las Vegas algorithm with an expected update time of $O( \lceil \frac{\sqrt{m}}{βk} \rceil )$ rounds that maintains a $\frac{2}{3}$-approximate maximum matching that is also maximal, where $m$ is the number of edges in the graph and $β$ is the available link bandwidth. For batch-dynamic updates, where the adversary may insert up to $\ell\ge 1$ edges at once, we prove the following. There is a randomized algorithm that succeeds with high probability in maintaining a $\frac{2}{3}$-approximate maximum matching and has a worst case update time of $O(\lceil\frac{\ell\log n}{\sqrt{βk}}\rceil )$ rounds. Any algorithm for maintaining a maximal matching without 3-augmenting paths under batches of $\ell$-edge insertions has an update time of $Ω( \frac{\ell}{βk \log n} )$ rounds in the worst case. |
| title | Dynamic Approximate Maximum Matching in the Distributed Vertex Partition Model |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 68W15 |
| url | https://arxiv.org/abs/2504.17338 |