A Space-space Trade-off for Directed st-Connectivity
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914347567022080 |
|---|---|
| author | Edenhofer, Roman |
| author_facet | Edenhofer, Roman |
| contents | We prove a space-space trade-off for directed $st$-connectivity in the catalytic space model. For any integer $k \leq n$, we give an algorithm that decides directed $st$-connectivity using $O(\log n \cdot \log k+\log n)$ regular workspace and $O\left(\frac{n}{k} \cdot \log^2 n\right)$ bits of catalytic memory. This interpolates between the classical $O(\log^2 n)$-space bound from Savitch's algorithm and a catalytic endpoint with $O(\log n)$ workspace and $O(n\cdot \log^2 n)$ catalytic memory.
As a warm-up, we present a catalytic variant of Savitch's algorithm achieving the endpoint above. Up to logarithmic factors, this matches the smallest catalyst size currently known for catalytic logspace algorithms, due to Cook and Pyne (ITCS 2026). Our techniques also extend to counting the number of walks from $s$ to $t$ of a given length $\ell\leq n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_21088 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Space-space Trade-off for Directed st-Connectivity Edenhofer, Roman Data Structures and Algorithms Computational Complexity We prove a space-space trade-off for directed $st$-connectivity in the catalytic space model. For any integer $k \leq n$, we give an algorithm that decides directed $st$-connectivity using $O(\log n \cdot \log k+\log n)$ regular workspace and $O\left(\frac{n}{k} \cdot \log^2 n\right)$ bits of catalytic memory. This interpolates between the classical $O(\log^2 n)$-space bound from Savitch's algorithm and a catalytic endpoint with $O(\log n)$ workspace and $O(n\cdot \log^2 n)$ catalytic memory. As a warm-up, we present a catalytic variant of Savitch's algorithm achieving the endpoint above. Up to logarithmic factors, this matches the smallest catalyst size currently known for catalytic logspace algorithms, due to Cook and Pyne (ITCS 2026). Our techniques also extend to counting the number of walks from $s$ to $t$ of a given length $\ell\leq n$. |
| title | A Space-space Trade-off for Directed st-Connectivity |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2602.21088 |