1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What did you try? Where did you get stuck? In particular, did you try your proposed algorithm on any graphs? Did you think about what graphs might break it or why it might be correct? It seems likely that using DFS on the reverse graph is necessary: it would be really weird to write an algorithm that unnecessarily used the reversal of the graph. $\endgroup$ – David Richerby Oct 23 '15 at 9:28
  • 1
    $\begingroup$ I have some downtime this afternoon, so I'm tempted to look for counterexamples as a kind of puzzle; but I think it's more important for you to understand the point Yuval is making. $\endgroup$ – G. Bach Oct 23 '15 at 14:16
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ here is a simpler one: $V=\{a,b,c\}\ E=\{ab,ba,ac\}$. Then dfs from a : a,b,a,c. finish times: b,c,a. scc={b,a,c} where as correct answer is {b,a},{c}. $\endgroup$ – emmy Oct 25 '15 at 2:30
  • $\begingroup$ Thanks a lot :) and can you please tell how you came to this counter example ? $\endgroup$ – JVJ Oct 25 '15 at 3:30
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ youtu.be/Cy_0aInLOHE?list=PLLH73N9cB21W1TZ6zz1dLkyIm50HylGyg .The proof so provide for kosaraju algo by proff. tim roughgarden can also be applied to the modified algo I've thought of. Concept of metagraph I mean. $\endgroup$ – JVJ Oct 23 '15 at 15:13
  • $\begingroup$ @JVJ, I doubt it. If you think so, try editing your question to include your proposed proof of correctness for your proposed algorithm -- but I very much doubt that you have a valid proof of correctness for your proposed algorithm. $\endgroup$ – D.W. Oct 23 '15 at 16:39
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Don't write the same answer to two different questions. In particular, it seems that you copied this answer from the other one, thus losing the link. $\endgroup$ – Yuval Filmus Feb 8 at 6:03
  • $\begingroup$ They are the same questions, both are my answers and I didn't lose the link, it's just the emmy's answer is here, so no need to link it, use ctrl+f to find it. So unless I am breaking some rule of stackexchange I don't see a problem with what I did. $\endgroup$ – K. Ali Feb 8 at 16:51
  • $\begingroup$ BTW If I am breaking a rule that says I can't use the same answers to the same questions, please point it out to me so that I'll be careful next time. $\endgroup$ – K. Ali Feb 8 at 17:02
  • $\begingroup$ I would say this is discouraged. If people interact with you regarding one answer, via comments, people reading the other answer won't be aware of it. $\endgroup$ – Yuval Filmus Feb 8 at 17:06
  • $\begingroup$ That's a good point. I think someone already added a link to this question as a comment on the other question which is good since I can't unless I have 50 reputations. I'll delete the other answer $\endgroup$ – K. Ali Feb 8 at 17:21

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.