Performing Transitive Reduction via neighbourhood and strongly connected components

Question

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?

Answer 1

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.

The procedure you describe appears to involve deleting vertices. Therefore, it does not appear to match the standard definition of transitive reduction. (Perhaps your book has a non-standard definition of transitive reduction; if so, you might need to edit your question to ask about it.)

That said, a related construction does appear to correctly provide the transitive reduction. In the related construction, instead of collapsing all vertices in a SCC into a single vertex, we replace the SCC with a directed cycle; then we apply transitive reduction to the dag of SCCs. It is possible that your textbook actually uses the following procedure: (1) shrink each SCC to a single vertex, (2) apply transitive reduction to the resulting graph (which is the dag of SCCs), (3) now take each shrunken vertex and restore all of the original vertices and turn it into a directed cycle. That should provide a correct algorithm for transitive reduction. If that is what the book had in mind, your mistake was that you failed to perform step (3): you performed steps (1) and (2) and stopped there. Of course, you have to perform the full procedure to get the full transitive reduction.

You might also be interested in the notion of a minimum equivalent graph, which involves deleting both edges and vertices; however, finding it in general is NP-hard.