# Approximating transitive reduction of a transitive closure of a dag

Let's suppose a transitive closure $G^+$ of a dag $G$ is given and we want to compute an approximation of the transitive reduction $G^-$ such that the full transitive reduction is a subgraph of the approximation.

My idea is to compute a topological sort $TS$ of the dag and then for each edge $u \rightarrow v$ look at ~10 nodes $w$ such that $TS(w) > TS(v)$, $u \rightarrow w$ and $TS(w)$ are as large as possible. If $w \rightarrow v$ then edge $u \rightarrow v$ is redundant ($u \rightarrow w \rightarrow v$) and can be removed.

An implementation of this algorithm can be found here. The algorithm has complexity $O(m + n)$ and from my experiments the number of edges in the approximation is 3-5 times larger than in the full transitive reduction.

I have a couple of questions:

• Can I prove any upper bound for the number of edges in the approximation?
• How can I improve the algorithm (except looking at more $w$-s) in terms of time and/or number of edges left?
• what does "approximation" mean in this context ? and what's a transitive reduction ? – Suresh Venkat Jan 20 '11 at 17:52
• @Suresh: Trasitive reduction is described here en.wikipedia.org/wiki/Transitive_reduction . We know that transitive reduction of a transitive closure is unique. Approximation means a graph A such that the transitive reduction is a subgraph of A (ie. A has some extra edges compared to A). – Alexandru Jan 21 '11 at 11:50
• I cannot understand what the algorithm does. You write “for each edge u→v look at […].” But clearly “looking at” something does not affect the graph. I guess that you remove some edges from the input graph under certain conditions, but which edges and when? – Tsuyoshi Ito Jan 29 '11 at 3:28
• @Ito: Improved the explanation. Let me know if I missed anything else. – Alexandru Jan 29 '11 at 15:59
• You might be interested in Size-Estimation Framework with Applications to Transitive Closure and Reachability by Edith Cohen. It's about the related problem of quickly estimating the number of nodes reachable from given nodes in a given directed graph... And possibly Approximating the Minimum Equivalent Digraph (given an arbitrary directed graph, find an approximately minimum-size subgraph that preserves all reachability relations between vertex pairs). – Neal Young Aug 10 '14 at 3:59

Due to [Aho, Garey, and Ullman, The transitive reduction of a directed graph, 1972]; $G^t = G - GG^+$, where $G^t$ is the transitive reduction of $G$. In this particular case, $G = G^+$. So, we can conclude $G^t = G - G^2$. Although this result does not lead to a linear non-approximate algorithm, I hope such an observation would be helpful in this context.