1
$\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$
  • $\begingroup$ What do you mean by "is $v$ reachable from $u$"? What is $v$? Do you want this information for all $v$? $\endgroup$ – Yuval Filmus Aug 11 '17 at 10:43
  • $\begingroup$ Also, is $G$ directed or undirected? $\endgroup$ – Yuval Filmus Aug 11 '17 at 10:43
  • $\begingroup$ What machine model are you assuming? Random-access machine operating on machine words? $\endgroup$ – Yuval Filmus 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$ – aaag 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.