7
$\begingroup$

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?
| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ what does "approximation" mean in this context ? and what's a transitive reduction ? $\endgroup$ – Suresh Venkat Jan 20 '11 at 17:52
  • $\begingroup$ @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). $\endgroup$ – Alexandru Jan 21 '11 at 11:50
  • 1
    $\begingroup$ 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? $\endgroup$ – Tsuyoshi Ito Jan 29 '11 at 3:28
  • $\begingroup$ @Ito: Improved the explanation. Let me know if I missed anything else. $\endgroup$ – Alexandru Jan 29 '11 at 15:59
  • $\begingroup$ 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). $\endgroup$ – Neal Young Aug 10 '14 at 3:59
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.