# Transitive Reduction Problem of Directed Graphs (Transitive Reduction Problem)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Description

A directed graph $G^t$ is said to be a transitive reduction of the directed graph $G$ provided that (i) $G$ has a directed path from vertex $u$ to vertex $v$ if and only if $G$ has a directed path from vertex $u$ to vertex $v$, and (ii) there is no graph with fewer arcs than $G^t$ satisfying condition (i). The problem asks to find such a graph $G^t$ for a given digraph $G$.

## Parameters

$n$: number of vertices

$m$: number of edges

## Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Aho, Garey & Ullman 1972 $O(n^omega)$ where omega is the exponent on boolean matrix multiplication $O(n^{2})$ Exact Deterministic Time
Aho, Garey & Ullman 1972 $O(n^{2.807})$ $O(n^{2})$ Exact Deterministic Time
Aho, Garey & Ullman 1978 $O(n^{2.8})$ $O(n^{2})$ Exact Deterministic Time
Aho, Garey & Ullman 1979 $O(n^{2.78})$ $O(n^{2})$ Exact Deterministic Time
Aho, Garey & Ullman 1980 $O(n^{2.52})$ $O(n^{2})$ Exact Deterministic Time
Aho, Garey & Ullman 1980 $O(n^{2.518})$ $O(n^{2})$ Exact Deterministic Time
Aho, Garey & Ullman 1981 $O(n^{2.495})$ $O(n^{2})$ Exact Deterministic Time
Aho, Garey & Ullman 1986 $O(n^{2.48})$ $O(n^{2})$ Exact Deterministic Time
Aho, Garey & Ullman 1990 $O(n^{2.372})$ $O(n^{2})$ Exact Deterministic Time
Aho, Garey & Ullman 2014 $O(n^{2.373})$ $O(n^{2})$ Exact Deterministic Time
Aho, Garey & Ullman 2014 $O(n^{2.371})$ $O(n^{2})$ Exact Deterministic Time
Gries, Martin 1989 $O(n^{3})$ $O(n^{2})$ Exact Deterministic Time