Streaming Maximal Matching with Bounded Deletions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910838189719552 |
|---|---|
| author | Khanna, Sanjeev Konrad, Christian Dark, Jacques |
| author_facet | Khanna, Sanjeev Konrad, Christian Dark, Jacques |
| contents | We initiate the study of the Maximal Matching problem in bounded-deletion graph streams. In this setting, a graph $G$ is revealed as an arbitrary sequence of edge insertions and deletions, where the number of insertions is unrestricted but the number of deletions is guaranteed to be at most $K$, for some given parameter $K$. The single-pass streaming space complexity of this problem is known to be $Θ(n^2)$ when $K$ is unrestricted, where $n$ is the number of vertices of the input graph. In this work, we present new randomized and deterministic algorithms and matching lower bound results that together give a tight understanding (up to poly-log factors) of how the space complexity of Maximal Matching evolves as a function of the parameter $K$: The randomized space complexity of this problem is $\tildeΘ(n \cdot \sqrt{K})$, while the deterministic space complexity is $\tildeΘ(n \cdot K)$. We further show that if we relax the maximal matching requirement to an $α$-approximation to Maximum Matching, for any constant $α> 2$, then the space complexity for both, deterministic and randomized algorithms, strikingly changes to $\tildeΘ(n + K)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_15330 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Streaming Maximal Matching with Bounded Deletions Khanna, Sanjeev Konrad, Christian Dark, Jacques Data Structures and Algorithms We initiate the study of the Maximal Matching problem in bounded-deletion graph streams. In this setting, a graph $G$ is revealed as an arbitrary sequence of edge insertions and deletions, where the number of insertions is unrestricted but the number of deletions is guaranteed to be at most $K$, for some given parameter $K$. The single-pass streaming space complexity of this problem is known to be $Θ(n^2)$ when $K$ is unrestricted, where $n$ is the number of vertices of the input graph. In this work, we present new randomized and deterministic algorithms and matching lower bound results that together give a tight understanding (up to poly-log factors) of how the space complexity of Maximal Matching evolves as a function of the parameter $K$: The randomized space complexity of this problem is $\tildeΘ(n \cdot \sqrt{K})$, while the deterministic space complexity is $\tildeΘ(n \cdot K)$. We further show that if we relax the maximal matching requirement to an $α$-approximation to Maximum Matching, for any constant $α> 2$, then the space complexity for both, deterministic and randomized algorithms, strikingly changes to $\tildeΘ(n + K)$. |
| title | Streaming Maximal Matching with Bounded Deletions |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.15330 |