Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Basic Graph Algorithms > Transitive Closure and Transitive Reduction

## Transitive Closure and Transitive Reduction

### What is the Transitive Closure of a Graph?

The transitive closure of a directed graph `G=(V,E)` is a graph `H=(V,F)` with edge `(v,w)` in `F` if and only if there is a path from `v` to `w` in `G`.

### Where can I use Transitive Closure?

It is very easy to check if there is a path from a node `v` to a node `w` in `G` using the transitive closure `H` of a graph `G` . There is a path in `G` if and only if there is an edge `(v,w)` in `H`.

### Transitive Reduction

Besides functions to compute the transitive closure of a graph, LEDA also offers functions to compute the transitive reduction of a graph. The transitive reduction of a directed graph `G=(V,E)` is a graph `H=(V,F)` where `F` is a minimal subset of `E` such that `G` and `H` have the same transitive closure.

Notice that transitive closure and transitive reduction are not exact reversals of each other. If I compute the transitive closure H of a graph G and then compute the transitive reduction G' of H, G' may be a subgraph of G.

### Running Time

The running time for transitive closure and transitive reduction is O(|V||E|).

Basic Graph Algorithms

Graphs and Related Data Types

GraphWin for visualizing graphs and graph algorithms

Manual Entries:

Manual Page Basic Graph Algorithms