What is the best known transitive closure algorithm for a directed graph?

Question

In terms of runtime, what is the best known transitive closure algorithm for directed graphs?

I am currently using Warshall's algorithm but its O(n^3). Although, due to the graph representation my implementation does slightly better (instead of checking all edges, it only checks all out going edges). Is there any transitive closure algorithm which is better than this? In particular, is there anything specifically for shared memory multi-threaded architectures?

Answer 1

This paper discusses the performance of various transitive closure algorithms:

http://www.vldb.org/conf/1988/P382.PDF

One interesting idea from the paper is to avoid recomputing the entire closure as the graph changes.

There is also this page by Esko Nuutila, which lists a couple of more recent algorithms:

http://www.cs.hut.fi/~enu/tc.html

His PhD thesis listed on that page may be the best place to start:

http://www.cs.hut.fi/~enu/thesis.html

From that page:

The experiments also indicate that with the interval representation and the new algorithms, the transitive closure can be computed typically in time linear to the size of the input graph.

Answer 2

The Algorithm Design manual has some useful information. Key points:

• Transitive closure is as difficult as matrix multiplication; so the best known bound is the Coppersmith–Winograd algorithm which runs in O(n^2.376), but in practice it's probably not worthwhile to use matrix multiplication algorithms.
• For a heuristic speedup, calculate strongly connected components first.