A Quantum Time-Space Tradeoff for Directed $st$-Connectivity

Stacey Jeffery, Galina Pass

Directed $st$-connectivity (DSTCON) is the problem of deciding if there exists a directed path between a pair of distinguished vertices $s$ and $t$ in an input directed graph. This…