Transitive Reduction Problem of Directed Graphs (Transitive Reduction Problem)

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

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff

References/Citation

https://epubs.siam.org/doi/pdf/10.1137/0201008