1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Sep 3 '14 at 7:33
  • $\begingroup$ @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 :). $\endgroup$ – RAbraham Sep 3 '14 at 12:05
  • $\begingroup$ 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. $\endgroup$ – D.W. Sep 3 '14 at 15:27
  • $\begingroup$ @D.W. I have edited the question with EDIT:EXAMPLE. Let me know if I can provide more information $\endgroup$ – RAbraham Sep 3 '14 at 19:26
1
$\begingroup$

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.

$\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.