Deterministic Independent Sets in the Semi-Streaming Model
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913689677856768 |
|---|---|
| author | Ye, Daniel |
| author_facet | Ye, Daniel |
| contents | We consider the independent set problem in the semi-streaming model. For any input graph $G=(V, E)$ with $n$ vertices, an independent set is a set of vertices with no edges between any two elements. In the semi-streaming model, $G$ is presented as a stream of edges and any algorithm must use $\tilde O(n)$ bits of memory to output a large independent set at the end of the stream.
Prior work has designed various semi-streaming algorithms for finding independent sets. Due to the hardness of finding maximum and maximal independent sets in the semi-streaming model, the focus has primarily been on finding independent sets in terms of certain parameters, such as the maximum degree $Δ$. In particular, there is a simple randomized algorithm that obtains independent sets of size $\frac n{Δ+1}$ in expectation, which can also be achieved with high probability using more complicated algorithms. For deterministic algorithms, the best bounds are significantly weaker. In fact, the best we currently know is a straightforward algorithm that finds an $\tildeΩ\left(\frac n{Δ^2}\right)$ size independent set.
We show that this straightforward algorithm is nearly optimal by proving that any deterministic semi-streaming algorithm can only output an $\tilde O\left(\frac n{Δ^2}\right)$ size independent set. Our result proves a strong separation between the power of deterministic and randomized semi-streaming algorithms for the independent set problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09440 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deterministic Independent Sets in the Semi-Streaming Model Ye, Daniel Data Structures and Algorithms Computational Complexity We consider the independent set problem in the semi-streaming model. For any input graph $G=(V, E)$ with $n$ vertices, an independent set is a set of vertices with no edges between any two elements. In the semi-streaming model, $G$ is presented as a stream of edges and any algorithm must use $\tilde O(n)$ bits of memory to output a large independent set at the end of the stream. Prior work has designed various semi-streaming algorithms for finding independent sets. Due to the hardness of finding maximum and maximal independent sets in the semi-streaming model, the focus has primarily been on finding independent sets in terms of certain parameters, such as the maximum degree $Δ$. In particular, there is a simple randomized algorithm that obtains independent sets of size $\frac n{Δ+1}$ in expectation, which can also be achieved with high probability using more complicated algorithms. For deterministic algorithms, the best bounds are significantly weaker. In fact, the best we currently know is a straightforward algorithm that finds an $\tildeΩ\left(\frac n{Δ^2}\right)$ size independent set. We show that this straightforward algorithm is nearly optimal by proving that any deterministic semi-streaming algorithm can only output an $\tilde O\left(\frac n{Δ^2}\right)$ size independent set. Our result proves a strong separation between the power of deterministic and randomized semi-streaming algorithms for the independent set problem. |
| title | Deterministic Independent Sets in the Semi-Streaming Model |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2502.09440 |