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

• Please define "first part" and "k-th part". Also, as you have written it the answer is the direct product of the "first part" and "k-th part" (whatever they are) and why would you want to list the elements of a direct product one at a time? – Brendan McKay Nov 29 '11 at 11:13
• Thanks. I've edited my question. We have parts of the graph G_1, ..., G_k, where edges only go in one direction, and without skipping parts (say, from left to right - there are only edges from G_i to G_{i+1}). I want all pairs of a starting vertex (in G_1) and an end vertex (in G_k) with a path connecting them. – MrMulliner Nov 29 '11 at 11:19

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)$.
• Brendan, wouldn't a simpler worse-than-linear example simply have $n$ vertices in the first part connecting to a single vertex in the second part connecting to $n$ vertices in the third part? That has a total of $2n$ edges, but $n^2$ connected pairs $(s,t)$. (Of course the output there could be reduced to the sublinear answer "all of them.") – Barry Cipra Nov 29 '11 at 14:00
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.