Reducing redundant edges from a dependency graph I have a DAG of dependencies that contains lots of redundant edges (see example below). I want a "quick" algorithm (ie. can handle a graph with several thousands of nodes/edges) that finds a minimal sub graph. 

For example:

A -&gt; B -&gt; C
A -&gt; C


in words A is prerequisite to B, and B is prerequisite to C, and also A is prerequisite to C. In this case A -> C is redundant (since B is already necessary to reach C, and A is necessary to reach B).

Its been a while since I studied algorithms, and I'm not sure where to start.

By the way, its not critical that the algorithm finds the global minimum, local minimum is fine (the edge reduction is only a runtime optimization for next stage of processing).

Also, I realize this is a CS QA and not programming, but my program is written in Python, so I would be extra happy to learn of a python module or open source for doing this reduction, just in case you know of it.

thanks in advance!
The Transitive Reduction of a Directed Graph
A. V. Aho, M. R. Garey, and J. D. Ullman

According to wikipedia, this algorithm is used by tred which is tool for transitive reduction available in GraphViz package. You can run it on your graph and get reduced graph. 

This question is duplicate of this stackoverflow question.

code here graphviz/tools/src/tred.c does use DFS. ;-)