<p>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. </p>

CC BY-SA 3.0
2014-03-12T10:14:50.027Z
2014-03-12T10:14:50.027Z
ekayaaslan
<p>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.</p>

<p>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) &gt; 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.</p>

<p>An implementation of this algorithm can be found <a href="https://github.com/brtzsnr/structure/blob/master/src/main/java/ibis/structure/DAG.java#L341">here</a>. 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.</p>

<p>I have a couple of questions:</p>

<ul>
<li>Can I prove any upper bound for the number of edges in the approximation?</li>
<li>How can I improve the algorithm (except looking at more $w$-s) in terms of time and/or number of edges left?</li>
</ul>

CC BY-SA 2.5
2011-01-20T17:52:24.773Z
what does "approximation" mean in this context ? and what's a transitive reduction ?
Suresh Venkat
CC BY-SA 2.5
2011-01-21T11:50:02.573Z
@Suresh: Trasitive reduction is described here http://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
CC BY-SA 2.5
2011-01-29T03:28:50.810Z
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
CC BY-SA 2.5
2011-01-29T15:59:52.003Z
@Ito: Improved the explanation. Let me know if I missed anything else.
Alexandru
CC BY-SA 3.0
2014-08-10T03:59:06.303Z
You might be interested in [Size-Estimation Framework with Applications to Transitive Closure and Reachability](http://www.sciencedirect.com/science/article/pii/S0022000097915348) 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](http://arxiv.org/pdf/cs.DS/0205040.pdf) (given an arbitrary directed graph, find an approximately minimum-size subgraph that preserves all reachability relations between vertex pairs).
Neal Young
CC BY-SA 3.0
2014-08-10T04:23:42.480Z
1. What do you mean by "$TS(w) > TS(v)$"?  A-priori I would guess that you mean $w$ is after $v$ in the top. sort, but for your algorithm to work it seems you would want the opposite.  2. The link to code given in the post ("[here](https://github.com/brtzsnr/structure/blob/master/src/main/java/ibis/structure/DAG.java#L341)") seems to be not working (Aug 9).
Neal Young
<ds.algorithms><graph-algorithms><approximation-algorithms><transitive-closure><transitive-reduction>
Approximating transitive reduction of a transitive closure of a dag
Alexandru
# Approximating transitive reduction of a transitive closure of a dag

(Asked by: username_0 on 2011-01-20)

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](https://github.com/brtzsnr/structure/blob/master/src/main/java/ibis/structure/DAG.java#L341). 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?

**Tags:** ds.algorithms, graph-algorithms, approximation-algorithms, transitive-closure, transitive-reduction
> **Comments:**
> **username_1**: what does "approximation" mean in this context ? and what's a transitive reduction ?  
> **username_0**: @Suresh: Trasitive reduction is described here http://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).  
> **username_2**: 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?  
> **username_0**: @Ito: Improved the explanation. Let me know if I missed anything else.  
> **username_3**: You might be interested in [Size-Estimation Framework with Applications to Transitive Closure and Reachability](http://www.sciencedirect.com/science/article/pii/S0022000097915348) 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](http://arxiv.org/pdf/cs.DS/0205040.pdf) (given an arbitrary directed graph, find an approximately minimum-size subgraph that preserves all reachability relations between vertex pairs).  
> **username_3**: 1. What do you mean by "$TS(w) > TS(v)$"?  A-priori I would guess that you mean $w$ is after $v$ in the top. sort, but for your algorithm to work it seems you would want the opposite.  2. The link to code given in the post ("[here](https://github.com/brtzsnr/structure/blob/master/src/main/java/ibis/structure/DAG.java#L341)") seems to be not working (Aug 9).  

---

## 1 answers

### Answer by username_4 on 2014-03-12. Score: 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.


---

