A Space-space Trade-off for Directed st-Connectivity

Roman Edenhofer

We prove a space-space trade-off for directed $st$-connectivity in the catalytic space model. For any integer $k\le n$, we give an algorithm that decides directed $st$-connectivi…