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

<ul>
<li>$O(\log n)$ time and $O(n^3 \log n)$ work on a Common CRCW PRAM.</li>
<li>$O(\log^2 n)$ time and $O(n^\omega \log n)$ work on a CREW PRAM.</li>
</ul>

<p>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:</p>

<ul>
<li>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$.</li>
</ul>

CC BY-SA 2.5
2010-09-26T15:01:31.187Z
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
CC BY-SA 2.5
2010-09-27T02:03:20.050Z
Note that I said o(log^2{n}) not O(log^2{n}).
Shiva Kintali
CC BY-SA 2.5
2010-09-26T10:59:54.623Z
2010-09-26T10:59:54.623Z
Kristoffer Arnsfelt Hansen
<p>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: <a href="http://www.cs.brown.edu/~ws/papers/scc.pdf">http://www.cs.brown.edu/~ws/papers/scc.pdf</a> .</p>

CC BY-SA 2.5
2010-09-27T16:02:44.263Z
2010-09-27T16:02:44.263Z
Warren Schudy
<p>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&lt;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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-22T15:49:25.280Z
Can you please add the references.
Shiva Kintali
CC BY-SA 2.5
2010-09-23T08:22:50.607Z
I only know about O(log n) time on a CRCW PRAM. Was that what you meant?
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2010-09-24T12:39:30.497Z
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
CC BY-SA 2.5
2010-09-26T07:54:31.757Z
We need O(logn) iterations of matrix multiplication to solve st-connectivity.
Shiva Kintali
CC BY-SA 2.5
2010-09-26T18:08:10.403Z
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
CC BY-SA 2.5
2010-09-22T15:42:21.777Z
2010-09-28T01:04:39.920Z
2010-09-28T01:04:39.920Z
virgi
<p><a href="http://portal.acm.org/citation.cfm?id=314500.314562">Chong, Han and Lam</a> 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 <a href="http://en.wikipedia.org/wiki/St-connectivity">directed st-connectivity</a> ? 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 ?</p>

CC BY-SA 3.0
2015-07-13T02:12:08.167Z
If there is a directed $s-t$ path, is it possible to find it ?
Kumar
CC BY-SA 2.5
2010-09-21T22:36:06.750Z
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
CC BY-SA 2.5
2010-09-22T04:15:51.147Z
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
CC BY-SA 2.5
2010-09-22T20:42:41.487Z
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
<dc.parallel-comp>
Parallel algorithms for directed st-connectivity
Shiva Kintali
# Parallel algorithms for directed st-connectivity

(Asked by: username_0 on 2010-09-21)

[Chong, Han and Lam](http://portal.acm.org/citation.cfm?id=314500.314562) 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](http://en.wikipedia.org/wiki/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 ?

**Tags:** dc.parallel-comp

> **Comments:**
> **username_2**: 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?  
> **username_3**: 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.  
> **username_4**: With appropriate restrictions on the intruction set, O(log^i n) time on a CRCW PRAM is exactly uniform AC^i, for i>=1.  
> **username_1**: If there is a directed $s-t$ path, is it possible to find it ?  

---

## 3 answers

### Answer by username_6 on 2010-09-22. Score: 14 | Accepted answer

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.

> **Comments:**
> **username_0**: Can you please add the references.  
> **username_4**: I only know about O(log n) time on a CRCW PRAM. Was that what you meant?  
> **username_0**: O(logn) on CREW is great. Thats what I am looking for. I would like to accept your answer. Please add the reference.  
> **username_0**: We need O(logn) iterations of matrix multiplication to solve st-connectivity.  
> **username_6**: 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.  

---

### Answer by username_4 on 2010-09-26. Score: 8

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

> **Comments:**
> **username_0**: So, it seems finding an o(log^2{n}) time parallel algorithm on CREW PRAM for general directed graphs is an open problem.  
> **username_0**: Note that I said o(log^2{n}) not O(log^2{n}).  

---

### Answer by username_5 on 2010-09-27. Score: 6

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


---

