Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913553995268096 |
|---|---|
| author | Assadi, Sepehr Khanna, Sanjeev Kiss, Peter |
| author_facet | Assadi, Sepehr Khanna, Sanjeev Kiss, Peter |
| contents | In a very recent breakthrough, Behnezhad and Ghafari [FOCS'24] developed a novel fully dynamic randomized algorithm for maintaining a $(1-ε)$-approximation of maximum matching with amortized update time potentially much better than the trivial $O(n)$ update time. The runtime of the BG algorithm is parameterized via the following graph theoretical concept:
* For any $n$, define $ORS(n)$ -- standing for Ordered RS Graph -- to be the largest number of edge-disjoint matchings $M_1,\ldots,M_t$ of size $Θ(n)$ in an $n$-vertex graph such that for every $i \in [t]$, $M_i$ is an induced matching in the subgraph $M_{i} \cup M_{i+1} \cup \ldots \cup M_t$.
Then, for any fixed $ε> 0$, the BG algorithm runs in \[
O\left( \sqrt{n^{1+O(ε)} \cdot ORS(n)} \right) \] amortized update time with high probability, even against an adaptive adversary. $ORS(n)$ is a close variant of a more well-known quantity regarding RS graphs (which require every matching to be induced regardless of the ordering). It is currently only known that $n^{o(1)} \leqslant ORS(n) \leqslant n^{1-o(1)}$, and closing this gap appears to be a notoriously challenging problem.
In this work, we further strengthen the result of Behnezhad and Ghafari and push it to limit to obtain a randomized algorithm with amortized update time of \[
n^{o(1)} \cdot ORS(n) \] with high probability, even against an adaptive adversary. In the limit, i.e., if current lower bounds for $ORS(n) = n^{o(1)}$ are almost optimal, our algorithm achieves an $n^{o(1)}$ update time for $(1-ε)$-approximation of maximum matching, almost fully resolving this fundamental question. In its current stage also, this fully reduces the algorithmic problem of designing dynamic matching algorithms to a purely combinatorial problem of upper bounding $ORS(n)$ with no algorithmic considerations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_13573 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs Assadi, Sepehr Khanna, Sanjeev Kiss, Peter Data Structures and Algorithms In a very recent breakthrough, Behnezhad and Ghafari [FOCS'24] developed a novel fully dynamic randomized algorithm for maintaining a $(1-ε)$-approximation of maximum matching with amortized update time potentially much better than the trivial $O(n)$ update time. The runtime of the BG algorithm is parameterized via the following graph theoretical concept: * For any $n$, define $ORS(n)$ -- standing for Ordered RS Graph -- to be the largest number of edge-disjoint matchings $M_1,\ldots,M_t$ of size $Θ(n)$ in an $n$-vertex graph such that for every $i \in [t]$, $M_i$ is an induced matching in the subgraph $M_{i} \cup M_{i+1} \cup \ldots \cup M_t$. Then, for any fixed $ε> 0$, the BG algorithm runs in \[ O\left( \sqrt{n^{1+O(ε)} \cdot ORS(n)} \right) \] amortized update time with high probability, even against an adaptive adversary. $ORS(n)$ is a close variant of a more well-known quantity regarding RS graphs (which require every matching to be induced regardless of the ordering). It is currently only known that $n^{o(1)} \leqslant ORS(n) \leqslant n^{1-o(1)}$, and closing this gap appears to be a notoriously challenging problem. In this work, we further strengthen the result of Behnezhad and Ghafari and push it to limit to obtain a randomized algorithm with amortized update time of \[ n^{o(1)} \cdot ORS(n) \] with high probability, even against an adaptive adversary. In the limit, i.e., if current lower bounds for $ORS(n) = n^{o(1)}$ are almost optimal, our algorithm achieves an $n^{o(1)}$ update time for $(1-ε)$-approximation of maximum matching, almost fully resolving this fundamental question. In its current stage also, this fully reduces the algorithmic problem of designing dynamic matching algorithms to a purely combinatorial problem of upper bounding $ORS(n)$ with no algorithmic considerations. |
| title | Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.13573 |