Bewaard in:
| Hoofdauteurs: | , , |
|---|---|
| Formaat: | Preprint |
| Gepubliceerd in: |
2025
|
| Onderwerpen: | |
| Online toegang: | https://arxiv.org/abs/2507.17841 |
| Tags: |
Voeg label toe
Geen labels, Wees de eerste die dit record labelt!
|
| _version_ | 1866908605434822656 |
|---|---|
| author | Assadi, Sepehr Hoppenworth, Gary Sundaresan, Janani |
| author_facet | Assadi, Sepehr Hoppenworth, Gary Sundaresan, Janani |
| contents | In the semi-streaming model, an algorithm must process any $n$-vertex graph by making one or few passes over a stream of its edges, use $O(n \cdot \text{polylog }n)$ words of space, and at the end of the last pass, output a solution to the problem at hand. Approximating (single-source) shortest paths on undirected graphs is a longstanding open question in this model. In this work, we make progress on this question from both upper and lower bound fronts:
We present a simple randomized algorithm that for any $ε> 0$, with high probability computes $(1+ε)$-approximate shortest paths from a given source vertex in \[
O\left(\frac{1}ε \cdot n \log^3 n \right)~\text{space} \quad \text{and} \quad O\left(\frac{1}ε \cdot \left(\frac{\log n}{\log\log n} \right) ^2\right) ~\text{passes}.
\] The algorithm can also be derandomized and made to work on dynamic streams at a cost of some extra $\text{poly}(\log n, 1/ε)$ factors only in the space. Previously, the best known algorithms for this problem required $1/ε\cdot \log^{c}(n)$ passes, for an unspecified large constant $c$.
We prove that any semi-streaming algorithm that with large constant probability outputs any constant approximation to shortest paths from a given source vertex (even to a single fixed target vertex and only the distance, not necessarily the path) requires \[ Ω\left(\frac{\log n}{\log\log n}\right) ~\text{passes}. \] We emphasize that our lower bound holds for any constant-factor approximation of shortest paths. Previously, only constant-pass lower bounds were known and only for small approximation ratios below two.
Our results collectively reduce the gap in the pass complexity of approximating single-source shortest paths in the semi-streaming model from $\text{polylog } n$ vs $ω(1)$ to only a quadratic gap. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_17841 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Better Bounds for Semi-Streaming Single-Source Shortest Paths Assadi, Sepehr Hoppenworth, Gary Sundaresan, Janani Data Structures and Algorithms Computational Complexity In the semi-streaming model, an algorithm must process any $n$-vertex graph by making one or few passes over a stream of its edges, use $O(n \cdot \text{polylog }n)$ words of space, and at the end of the last pass, output a solution to the problem at hand. Approximating (single-source) shortest paths on undirected graphs is a longstanding open question in this model. In this work, we make progress on this question from both upper and lower bound fronts: We present a simple randomized algorithm that for any $ε> 0$, with high probability computes $(1+ε)$-approximate shortest paths from a given source vertex in \[ O\left(\frac{1}ε \cdot n \log^3 n \right)~\text{space} \quad \text{and} \quad O\left(\frac{1}ε \cdot \left(\frac{\log n}{\log\log n} \right) ^2\right) ~\text{passes}. \] The algorithm can also be derandomized and made to work on dynamic streams at a cost of some extra $\text{poly}(\log n, 1/ε)$ factors only in the space. Previously, the best known algorithms for this problem required $1/ε\cdot \log^{c}(n)$ passes, for an unspecified large constant $c$. We prove that any semi-streaming algorithm that with large constant probability outputs any constant approximation to shortest paths from a given source vertex (even to a single fixed target vertex and only the distance, not necessarily the path) requires \[ Ω\left(\frac{\log n}{\log\log n}\right) ~\text{passes}. \] We emphasize that our lower bound holds for any constant-factor approximation of shortest paths. Previously, only constant-pass lower bounds were known and only for small approximation ratios below two. Our results collectively reduce the gap in the pass complexity of approximating single-source shortest paths in the semi-streaming model from $\text{polylog } n$ vs $ω(1)$ to only a quadratic gap. |
| title | Better Bounds for Semi-Streaming Single-Source Shortest Paths |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2507.17841 |