Open question regarding the DFS
It is conjectured that $\mathsf{P} \neq \mathsf{NC}$, and so no $\mathsf{P}$-complete problem has polylogarithmic parallel algorithms. This in no way contradicts the existence of a linear time and space algorithm for DFS.