1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Brendan McKay
    Commented Nov 29, 2011 at 11:13
  • $\begingroup$ 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. $\endgroup$
    – MrMulliner
    Commented Nov 29, 2011 at 11:19

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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.") $\endgroup$
    – Barry Cipra
    Commented Nov 29, 2011 at 14:00
  • $\begingroup$ Yes, that would be simpler. $\endgroup$
    – Brendan McKay
    Commented Nov 29, 2011 at 23:44
0
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .