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 ?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ 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? $\endgroup$– Robin KothariSep 21, 2010 at 22:36
-
$\begingroup$ 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. $\endgroup$– Suresh VenkatSep 22, 2010 at 4:15
-
$\begingroup$ With appropriate restrictions on the intruction set, O(log^i n) time on a CRCW PRAM is exactly uniform AC^i, for i>=1. $\endgroup$– Kristoffer Arnsfelt HansenSep 22, 2010 at 20:42
-
$\begingroup$ If there is a directed $s-t$ path, is it possible to find it ? $\endgroup$– KumarJul 13, 2015 at 2:12
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
5
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.
-
1
-
$\begingroup$ I only know about O(log n) time on a CRCW PRAM. Was that what you meant? $\endgroup$ Sep 23, 2010 at 8:22
-
$\begingroup$ O(logn) on CREW is great. Thats what I am looking for. I would like to accept your answer. Please add the reference. $\endgroup$ Sep 24, 2010 at 12:39
-
$\begingroup$ We need O(logn) iterations of matrix multiplication to solve st-connectivity. $\endgroup$ Sep 26, 2010 at 7:54
-
$\begingroup$ 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. $\endgroup$– virgiSep 26, 2010 at 18:08
$\begingroup$
$\endgroup$
2
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$.
answered Sep 26, 2010 at 10:59
Kristoffer Arnsfelt HansenKristoffer Arnsfelt Hansen
4,1292 gold badges26 silver badges36 bronze badges
-
$\begingroup$ So, it seems finding an o(log^2{n}) time parallel algorithm on CREW PRAM for general directed graphs is an open problem. $\endgroup$ Sep 26, 2010 at 15:01
-
$\begingroup$ Note that I said o(log^2{n}) not O(log^2{n}). $\endgroup$ Sep 27, 2010 at 2:03
$\begingroup$
$\endgroup$
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 .
