$\tilde{O}(n^{1/3})$-Space Algorithm for the Grid Graph Reachability Problem

Ryo Ashida, Kotaro Nakagawa

The directed graph reachability problem takes as input an $n$-vertex directed graph $G=(V,E)$, and two distinguished vertices $s$ and $t$. The problem is to determine whether there…