It is an open question that whether $\mathsf{DFS\text{}}$ can be done in $O(m+n)$ time and $O(n)$ bits of space, where $n,m$ represent the number of vertices and edges in a undirected graph. see this for DFS

DFS for directed graph is known to be in RNC i.e. randomised NC. $\mathsf{DFS\text{}}$ also known to be $\mathsf{P\text{-}Complete}$ problem.

My question is what would happen if someone shows that $\mathsf{DFS\text{}}$ can be done in $O(n+m)$ time and in $O(n)$ bits of space?Is it likely in that situation for DFS to admit polyloga-rithmically fast, parallel algorithm using only polynomial resources (see this research paper)?

  • $\begingroup$ What do you mean by polylogarithmically fast? Polylogarithmically of what? Of number of vertices? You are asking if it will be in $\mathsf{NC}$? $\endgroup$ – rus9384 Aug 27 '17 at 11:19
  • $\begingroup$ Polyloga-rithmically means running time $Poly (\ log n)$ , polynomial in logarithmic of $n$, where $n$ is the number of nodes in the graph. $\endgroup$ – Complexity Aug 27 '17 at 11:47
  • $\begingroup$ In fact I don't think that this will imply such result. HornSAT can be solved in $\Theta(n)$ time and there is no way to speed it up on classic machine. It is assumed that you can't parallelise it in worst case and same applies for DFS even if it can be sped up. $\endgroup$ – rus9384 Aug 27 '17 at 11:49
  • $\begingroup$ Why do you think that is an open question? What is your source for that? I don't see any such statement in the link you give (which is just to the Wikipedia page on DFS; it doesn't say anything like that). $\endgroup$ – D.W. Aug 27 '17 at 17:31

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.


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.