A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber · SIAM Journal on Computing · 1998
Directed s-t connectivity is the problem of detecting whether there is a path from vertex s to vertex t in a directed graph. We present the first known deterministic sublinear space, polynomial time algorithm for directed s-t connectivity. For n-vertex graphs, our algorithm can use as little as $n/2^{\Theta(\sqrt{\log n})}$ space while still running in polynomial time.