Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 9 down vote favorite
1

Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors. What is the best known parallel algorithm for directed st-connectivity ? Please state the running time, deterministic/randomized algorithm and the PRAM model used (assuming the number of processors is polynomial). Are there any $o({\log}^2{n})$ time parallel algorithms known for any special cases of directed st-connectivity ?

share|improve this question
Wikipedia says poly(n) processors + polylog time on a EREW PRAM is the same as NC. I'm not very familiar with the EREW PRAM model, but is there a connection between $(\log n)^i$ time (and polynomially many processors) and $NC^i$? In other words, is there a way to rephrase your question in terms of bounded-depth circuits? – Robin Kothari Sep 21 '10 at 22:36
the different parallel RAM models are equivalent upto log factors, so while EREW PRAM matches NC, this might not be true for specific log powers. – Suresh Venkat♦ Sep 22 '10 at 4:15
With appropriate restrictions on the intruction set, O(log^i n) time on a CRCW PRAM is exactly uniform AC^i, for i>=1. – Kristoffer Arnsfelt Hansen Sep 22 '10 at 20:42

3 Answers

up vote 10 down vote accepted

Directed s-t reachability can easily be done using O($n^3$) processors and O$(\log n$) time on a CRCW-PRAM, or in O($n^\omega$) processors and O($\log^2 n$) time on a EREW-PRAM where $\omega<2.376$ is the matrix multiplication exponent and $n$ is the number of vertices. The following paper claims O($n^\omega$) and O($\log n$) time on a CREW-PRAM: "Optimal Parallel Algorithms for Transitive Closure and Point Location in Planar Structures" by Tamassia and Vitter. Other papers claim the same thing and cite the Karp and Ramachandran survey (Parallel algorithms for shared-memory machines, in: J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science). The survey itself does mention that transitive closure is in AC1 and hence can be solved in O(log n) time on a CRCW-PRAM, but the part about CREW-PRAM is missing.

All Strassen-like algorithms for matrix multiplication (including the one by Coppersmith-Winograd) are essentially parallel algorithms that run in O$(\log n)$ time; transitive closure incurs an extra log (but if you allow unbounded fan-in the trivial O($n^3$) matrix mult can be done in constant depth and so reachability is in O$(\log n)$ time on a CRCW-PRAM). It's an open problem to improve the number of processors from the current best ~$n^{2.376}$; it is also a major open problem if reachability is in NC1, as it would imply L=NL among other things.

share|improve this answer
Can you please add the references. – Shiva Kintali Sep 22 '10 at 15:49
I only know about O(log n) time on a CRCW PRAM. Was that what you meant? – Kristoffer Arnsfelt Hansen Sep 23 '10 at 8:22
O(logn) on CREW is great. Thats what I am looking for. I would like to accept your answer. Please add the reference. – Shiva Kintali Sep 24 '10 at 12:39
We need O(logn) iterations of matrix multiplication to solve st-connectivity. – Shiva Kintali Sep 26 '10 at 7:54
In terms of parallel algorithms you do need O(log n) iterations of matrix mult to solve reachability; this is not the case for sequential algorithms as you can do some clever recursive things (see Fisher&Meyer'71). However, if your model of computation allows unbounded fan-in (as with AC1 and hence CRCW PRAM) matrix mult can be done in constant depth and so transitive closure can be done in logarithmic depth. – virgi Sep 26 '10 at 18:08
up vote 4 down vote

The book "An Introduction to Parallal Algorithms" by Joseph Jája (1992) lists the following results for transitive closure:

  • $O(\log n)$ time and $O(n^3 \log n)$ work on a Common CRCW PRAM.
  • $O(\log^2 n)$ time and $O(n^\omega \log n)$ work on a CREW PRAM.

As to the question of whether anything faster is known for special classes of graphs, Exercise 5.34 in the book gives the following example, where one can get $O(\log n)$ time on a CREW PRAM:

  • The class of directed acyclic graphs such that, for every two vertices $u$ and $v$, there is at most one path from $u$ to $v$.
share|improve this answer
So, it seems finding an o(log^2{n}) time parallel algorithm on CREW PRAM for general directed graphs is an open problem. – Shiva Kintali Sep 26 '10 at 15:01
Note that I said o(log^2{n}) not O(log^2{n}). – Shiva Kintali Sep 27 '10 at 2:03
up vote 3 down vote

Is you care about keeping the work small, not just polynomial, there is an elegant algorithm by Ullman and Yannakakis that allows for time/work tradeoffs. Table 1 in my paper on computing strongly connected components in parallel summarizes the parallel directed connectivity results I'm aware of: http://www.cs.brown.edu/~ws/papers/scc.pdf .

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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