Reachability in a k-partite graph Is there a known algorithm which runs in close to linear time, which receives a k-partite directed graph and outputs all pairs (s,t) where s is a vertex in the 'first' part of the graph and t is a vertex in the 'k-th' part?
EDIT: I wasn't specific enough. The assumption is that there are only edges between G_i and G_{i+1} for each i. This would be clear at first sight from a picture, and I haven't found a way to express it succinctly in words (suggestions are welcome).
EDIT: all pairs (s,t) ... such that there is a path from s to t.
 A: Firstly, the number of such pairs might be worse than linear in the number of edges.  Consider
three equal parts with the first two parts having vertices of out-degree $n^{1/2}$.  Then the number of edges is $O(n^{3/2})$ but the number of connected $(s,t)$ pairs can be $\Theta(n^2)$.
Secondly, the connection of each part to the next is described by a boolean matrix, and the
product of all the matrices describes the connection of the first part to the last.  So what you are asking for is the complexity of boolean matrix product. You'll find this to be a very well studied subject, maybe someone else can point us to a good recent survey.
A: Following up on Brendan's observation that the problem reduces
to Boolean matrix multiplication,
here is one useful algorithm (not the survey Brendan requests): 
M. Atkinson and N. Santoro,
"A practical algorithm for Boolean matrix multiplication,"
Information Processing Letters,
Volume 29, Issue 1, 15 September 1988, Pages 37-38:

An algorithm is given for multiplying two $n \times n$ Boolean matrices. It has time complexity $O(n^3/(\log n)^{3/2})$ and requires $n\log_2 n$ bits of auxiliary storage.

For recent references on sparse (and hypersparse) Boolean matrix multiplication, 
see the CSTheory question
"Fast sparse boolean matrix product with possible preprocessing."
