---
tag: 3PPAWFQ91B
kind: concept
name: Transitive reduction
sources:
  - wikipedia: en:3757117@r1343493340
    locator: Transitive reduction
    note: adopted
    mention: wikipedia://en/3757117
    sections: [Summary]
same_as:
  wikidata: Q3088151
  wikipedia: Transitive reduction
inventory: [SNKXYPR1ZG]
---

## Summary

In the mathematical field of graph theory, a **transitive reduction** of a [[directed graph|0KFYGSHHF5]] $D$ is another directed graph with the same vertices and as few edges as possible, such that for all pairs $v$, $w$ of vertices, a (directed) [[path|03NAMV1DHJ]] from $v$ to $w$ in $D$ exists if and only if such a path exists in the reduction. Transitive reductions were introduced by (Aho Garey Ullman 1972), who provided tight bounds on the computational complexity of constructing them.