Kosaraju's Algorithm-Strongly connected components

Question

In Kosaraju's Algorithm, using first dfs (traversing on reverse graph) we calculate finishing time of nodes, and then traverse (actual graph) in reverse order of finishing times. why not without reversing graph, using first dfs (traversing on actual graph) we calculate finishing time of nodes, and then traverse (actual graph) in actual order of finishing times. In case my proposed method is wrong please provide me with a counter example.

Answer 1

Consider a graph on $V= \{a,b,c,d,e,f,g,h\}$ with edges $ E=\{ab,ba,cd,dc,ef,fe,gh,hg,be,fh,ad,dg\}$ wherew $uv$ means an edges from u to v.
Applying your algo:

a valid dfs traversal : a,b,e,f,h,g,h,f,e,b,a,d,c,d,(g already done),a

vertex according to finish time : g,h,f,e,b,c,d,a

scc according to your algo : $\{g,h\},\{f,e\},\{b,a,d,c\}$

correct answer : $\{g,h\},\{e,f\},\{a,b\},\{c,d\}$.

Answer 2

What separates theoretical computer science from more applied areas within computer science is the notion of proof. If an algorithm claims to do something, we want proof that it does so, preferably a mathematical proof. (In rare occasions, experiments are also accepted.) We work under the maxim an algorithm doesn't work unless it is proved to work, whereas you seem to be working under the maxim an algorithm works unless we can find a counterexample.

For these reasons, I don't find it a good use of my time to find a counterexample. If you did want to find a counterexample yourself, there are several things to try. First, you can try a few random graphs; often this works. Second, you can try to concoct a parametric situation and determine parameters that defat your algorithm; this seems harder to apply in your case since your edges are not weighted, and so the parameters are too discrete. Third, you can try to prove that your algorithm works, fail at some step, and produce a counterexample as part of the process. Fourth, you can play with your algorithm on several graphs until you get an intuitive understanding of what it does, and given this understanding try to construct a counterexample. Fifth, if you really believe that the algorithm doesn't work but can't use any of the preceding method, treat it as a research project and use your research skills to construct a counterexample.

Kosaraju's algorithm is that way that it is for a reason. If a simpler or more intuitive algorithm worked, probably by now people would have discovered it, and it would be known. The fact that we still teach Kosaraju's algorithm suggests that similar but simpler algorithms don't work. That's why I'm pretty sure that your algorithm doesn't work, even without reading it. Of course, I can be wrong. To prove me wrong, all you have to do is to prove that your algorithm works.

Answer 3

For Kosaraju's algorithm to work you need to pick the components in the correct order starting from the sink SCC and work your way backward until you reach the source SCC. so basically you need to start with a node in the sink SCC.

Now let's define two claims

claim1: DFS guarantees that the node with the biggest finishing time will be in the source SCC.

claim2: DFS guarantees that the node with the smallest finishing time will be in the sink SCC.

Kosaraju's algorithm depends on the correctness of claim1. Because when you transpose a graph, the source SCC becomes the sink and vice versa so the node with the biggest finishing time, which is guaranteed by claim1 to be in the source of the transposed graph, must be in the sink SCC of the original graph.

For your modification to work, claim2 (not claim1) needs to be true. A counterexample to claim2 would be any graph where you start the DFS from the node that lies on the edge the connects two SCCs, like any of the examples by emmy.