Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913452854870016 |
|---|---|
| author | Assadi, Sepehr Behnezhad, Soheil Konrad, Christian Naidu, Kheeran K. Sundaresan, Janani |
| author_facet | Assadi, Sepehr Behnezhad, Soheil Konrad, Christian Naidu, Kheeran K. Sundaresan, Janani |
| contents | A semi-streaming algorithm in dynamic graph streams processes any $n$-vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph and using $O(n \cdot \mbox{polylog}(n))$ space. Semi-streaming algorithms for dynamic streams were first obtained in the seminal work of Ahn, Guha, and McGregor in 2012, alongside the introduction of the graph sketching technique, which remains the de facto way of designing algorithms in this model and a highly popular technique for designing graph algorithms in general.
We settle the pass complexity of approximating maximum matchings in dynamic streams via semi-streaming algorithms by improving the state-of-the-art in both upper and lower bounds.
We present a randomized sketching based semi-streaming algorithm for $O(1)$-approximation of maximum matching in dynamic streams using $O(\log\log{n})$ passes. The approximation ratio of this algorithm can be improved to $(1+ε)$ for any fixed $ε> 0$ even on weighted graphs using standard techniques. This exponentially improves upon several $O(\log{n})$ pass algorithms developed for this problem since the introduction of the dynamic graph streaming model.
In addition, we prove that any semi-streaming algorithm (not only sketching based) for $O(1)$-approximation of maximum matching in dynamic streams requires $Ω(\log\log{n})$ passes. This presents the first multi-pass lower bound for this problem, which is already also optimal, settling a longstanding open question in this area. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_21005 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams Assadi, Sepehr Behnezhad, Soheil Konrad, Christian Naidu, Kheeran K. Sundaresan, Janani Data Structures and Algorithms Computational Complexity A semi-streaming algorithm in dynamic graph streams processes any $n$-vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph and using $O(n \cdot \mbox{polylog}(n))$ space. Semi-streaming algorithms for dynamic streams were first obtained in the seminal work of Ahn, Guha, and McGregor in 2012, alongside the introduction of the graph sketching technique, which remains the de facto way of designing algorithms in this model and a highly popular technique for designing graph algorithms in general. We settle the pass complexity of approximating maximum matchings in dynamic streams via semi-streaming algorithms by improving the state-of-the-art in both upper and lower bounds. We present a randomized sketching based semi-streaming algorithm for $O(1)$-approximation of maximum matching in dynamic streams using $O(\log\log{n})$ passes. The approximation ratio of this algorithm can be improved to $(1+ε)$ for any fixed $ε> 0$ even on weighted graphs using standard techniques. This exponentially improves upon several $O(\log{n})$ pass algorithms developed for this problem since the introduction of the dynamic graph streaming model. In addition, we prove that any semi-streaming algorithm (not only sketching based) for $O(1)$-approximation of maximum matching in dynamic streams requires $Ω(\log\log{n})$ passes. This presents the first multi-pass lower bound for this problem, which is already also optimal, settling a longstanding open question in this area. |
| title | Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2407.21005 |