STCON in Directed Unique-Path Graphs

Sampath Kannan, Sanjeev Khanna & Sudeepa Roy
We study the problem of space-efficient polynomial-time algorithms for {\em directed st-connectivity} (STCON). Given a directed graph $G$, and a pair of vertices $s, t$, the STCON problem is to decide if there exists a path from $s$ to $t$ in $G$. For general graphs, the best polynomial-time algorithm for STCON uses space that is only slightly sublinear. However, for special classes of directed graphs, polynomial-time poly-logarithmic-space algorithms are known for STCON. In this paper,...