Approximating transitive reduction of a transitive closure of a dag

Question

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?

Answer 1

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.