Lower bound on space of DFS keeping the running time linear

Question

$\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 ?

Thanks in advance.

Answer 1

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.

What you are looking for is known as a time-space tradeoff, and these are not known for the RAM model, though similar results are known for restricted models such as the cell-probe model and comparison-based algorithms with memory (modeled as branching programs).

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.)