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.



Reachability in a k-partite graph
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.


