# Performing Transitive Reduction via neighbourhood and strongly connected components

I am trying to learn(self-study, not homework) how to perform transitive reduction according to what what Prof. Leskovec explains in section 10.8.6 in Mining Massive Datasets. The book is free to access online.

The section is actually talking about a way to perform transitive closure for a graph randomly choosing a node and determining it's strongly connected component(SCC). Though there are further steps on what to do next for using the above to calculate transitive closure, I want to focus on the SCC determination and its role in transitive reduction.

SCC is found for a node v with the following formula, Given a

• graph $G$ and it's reverse graph $G'$

• $N_G(v,\infty)$ indicates the neighbourhood of a node $v$ with radius $\infty$ i.e. all the nodes in the graph which can be reached by $v$

then the SCC with $v$ in it is given by $N_G(v,\infty) \bigcap N_{G'}(v,\infty)$

Once you find the SCC, collapse it to a single composite node( composite in the sense that information on which original node was collapsed is still retained) and then modify all the previous edges to point in or out to this single composite node. One repeats the above until the graph size is small and then we use that graph(and the SCC info to find transitive closure). That is the context of this question.

What I don't understand is below. It is mentioned that

We can iterate the above steps a fixed number of times. We can alternatively iterate until the graph becomes sufficiently small, or we could examine all nodes v in turn and not stop until each node is in an SCC by itself; i.e., NG(v, ∞) ∩ NG′ (v, ∞) = {v} for all remaining nodes v. If we make the latter choice, the resulting graph is called the transitive reduction of the original graph G.

I don't understand, for transitive reduction, how one can reduce to {v} without losing valid paths which can't be reduced.

P.S - My way of reducing the graph , is for every node v, delete $edge(v,a)$ if there exists $edge(n,a)$ for n in $N_G(v,\infty)$. There is 'currently' no need for SCC.

P.P.S - I am trying to implement this in Apache Spark for parallel computing. If you know of a more suitable algorithm, I would be happy if you could leave some pointers

EDIT: EXAMPLE 1 Consider a cycle with 4 nodes a,b,c,d. For $v=a$, $N_G(v,\infty) \bigcap N_{G'}(v,\infty)$ is ${a,b,c,d}$ According to the text, for transitive reduction, I have to reduce $N_G(v,\infty) \bigcap N_{G'}(v,\infty)$ to ${a}$. If I take out any of the edges,e.g. from $d$ to $a$ so that $N_G(v,\infty) \bigcap N_{G'}(v,\infty)$ is ${a}$ , it won't be a transitive reduction any more as there is no path from $d$ to $a$ as in the original path. Is my interpretation correct?

• What have you done on your own to try to understand? Have you tried working through a few examples by hand? Have you tried to construct a counterexample, i.e., a graph where this algorithm gives an incorrect result (loses valid paths)? The best way to understand is probably to start by trying that on your own.
– D.W.
Sep 3, 2014 at 7:33
• @D.W.I think I have spent close to 12 hours on this problem before posting. I have tried working through examples on my own and I actually came up with a possible solution(which I had mentioned in the P.S) and I am not an university student, just the average programmer in awe of CS :). Sep 3, 2014 at 12:05
• RAbraham, I still think you'll find it useful to try a few examples and see whether it works on them or not. See if you can construct a counterexample. That sometimes gives you enough insight that it all makes sense. If not, it might help you explain why you fear this might lose valid paths. After that the next thing would be to try to prove the correctness of this algorithm; you might tell us what proof outline you've tried and where you got stuck in completing the proof.
– D.W.
Sep 3, 2014 at 15:27
• @D.W. I have edited the question with EDIT:EXAMPLE. Let me know if I can provide more information Sep 3, 2014 at 19:26

The standard definition of the transitive reduction of a graph $G$ says that we delete as many edges as possible, to retain the same reachability relationships. However, the vertex set is unchanged: no vertices may be deleted.