2
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy