Efficient Catalytic Graph Algorithms
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908524484755456 |
|---|---|
| author | Cook, James Pyne, Edward |
| author_facet | Cook, James Pyne, Edward |
| contents | We give fast, simple, and implementable catalytic logspace algorithms for two fundamental graph problems.
First, a randomized catalytic algorithm for $s\to t$ connectivity running in $\widetilde{O}(nm)$ time, and a deterministic catalytic algorithm for the same running in $\widetilde{O}(n^3 m)$ time. The former algorithm is the first algorithmic use of randomization in $\mathsf{CL}$. The algorithm uses one register per vertex and repeatedly ``pushes'' values along the edges in the graph.
Second, a deterministic catalytic algorithm for simulating random walks which in $\widetilde{O}( m T^2 / \varepsilon )$ time estimates the probability a $T$-step random walk ends at a given vertex within $\varepsilon$ additive error. The algorithm uses one register for each vertex and increments it at each visit to ensure repeated visits follow different outgoing edges.
Prior catalytic algorithms for both problems did not have explicit runtime bounds beyond being polynomial in $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_06209 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Catalytic Graph Algorithms Cook, James Pyne, Edward Data Structures and Algorithms Computational Complexity We give fast, simple, and implementable catalytic logspace algorithms for two fundamental graph problems. First, a randomized catalytic algorithm for $s\to t$ connectivity running in $\widetilde{O}(nm)$ time, and a deterministic catalytic algorithm for the same running in $\widetilde{O}(n^3 m)$ time. The former algorithm is the first algorithmic use of randomization in $\mathsf{CL}$. The algorithm uses one register per vertex and repeatedly ``pushes'' values along the edges in the graph. Second, a deterministic catalytic algorithm for simulating random walks which in $\widetilde{O}( m T^2 / \varepsilon )$ time estimates the probability a $T$-step random walk ends at a given vertex within $\varepsilon$ additive error. The algorithm uses one register for each vertex and increments it at each visit to ensure repeated visits follow different outgoing edges. Prior catalytic algorithms for both problems did not have explicit runtime bounds beyond being polynomial in $n$. |
| title | Efficient Catalytic Graph Algorithms |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2509.06209 |