transitive reduction algorithm: pseudocode?

Question

I have been looking for an algorithm to perform a transitive reduction on a graph, but without success. There's nothing in my algorithms bible (Introduction To Algorithms by Cormen et al) and whilst I've seen plenty of transitive closure pseudocode, I haven't been able to track down anything for a reduction. The closest I've got is that there is one in "Algorithmische Graphentheorie" by Volker Turau (ISBN:978-3-486-59057-9), but unfortunately I don't have access to this book! Wikipedia is unhelpful and Google is yet to turn up anything. :^(

Does anyone know of an algorithm for performing a transitive reduction?

Answer 1

See Harry Hsu. "An algorithm for finding a minimal equivalent graph of a digraph.", Journal of the ACM, 22(1):11-16, January 1975. The simple cubic algorithm below (using an N x N path matrix) suffices for DAGs, but Hsu generalizes it to cyclic graphs.

// reflexive reduction for (int i = 0; i < N; ++i)   m[i][i] = false;  // transitive reduction for (int j = 0; j < N; ++j)   for (int i = 0; i < N; ++i)     if (m[i][j])       for (int k = 0; k < N; ++k)         if (m[j][k])           m[i][k] = false; 

Answer 2

The basic gist of the transitive reduction algorithm I used is

 foreach x in graph.vertices    foreach y in graph.vertices       foreach z in graph.vertices          delete edge xz if edges xy and yz exist  

The transitive closure algorithm I used in the same script is very similar but the last line is

          add edge xz if edges xy and yz OR edge xz exist