# Lower bound on space of DFS keeping the running time linear

$\mathsf{DFS(G, u) \text{}}$, $G = (V,E)$

Input : A Directed graph $G$ and a source vertex $u$.

Find : Is $v$ reachable from vertex $u$ for all $v \in V$ ?

Model of computation : Word RAM , one can represent a vector $A[1,\cdots ,n]$ of elements from a finite alphabet $\Sigma$ using $n \lg |\Sigma| + O(\lg^2 n)$ bits, such that any element of vector can be read or written in constant time.

$\mathsf{DFS \text{}}$ (Depth first search) takes $O(m + n)$ time and $O(n\log n)$ bits of space . Other known results for DFS is $O((m + n ) \log n)$ time and space $O(n)$ bits ( see this paper) (please note that DFS in this paper have defined as two phase process 1) Forward phase 2) Backtack phase )

It is a open question that $\mathsf{DFS \text{}}$ can be done in $O(m + n)$ time and $O(n)$ bits of space. (see this paper)

How to prove the lower bound that for $\mathsf{DFS \text{}}$ if we want to keep the runtime $O(m + n)$, we cannot do better than $O(n)$ in terms of space ?

• What do you mean by "is $v$ reachable from $u$"? What is $v$? Do you want this information for all $v$? Aug 11, 2017 at 10:43
• Also, is $G$ directed or undirected? Aug 11, 2017 at 10:43
• What machine model are you assuming? Random-access machine operating on machine words? Aug 11, 2017 at 10:45
• @ Yuval Filmus $v$ is reachable from $u$ means there is a path from vertex $u$ to vertex $v$.
– user35837
Aug 11, 2017 at 11:02

The questions as stated seems to be beyond reach. Without the time constraint, a superlogarithmic space lower bound on your question would imply that $\mathsf{L} \neq \mathsf{NL}$, a famous conjecture in complexity theory.
Time-space tradeoffs for reachability have been studied under the JAG model and its variants, which is a pebbling-based model. The best known time-space tradeoff, due to Edmonds and Poon, implies that polynomial time requires space roughly $\Omega(n/2^{O(\sqrt{\log n}})$, and this has been achieved by Barnes et al. in their paper A sublinear space, polynomial time algorithm for directed $s$-$t$ reachability. (The work of Edmonds and Poon is cited by Barnes et al.)