In Tarjan's SCC algorithm, the calculation of lowlink when encountering a vertex which is already on the stack is
// It says w.index not w.lowlink; that is deliberate and from the original paper v.lowlink := min(v.lowlink, w.index)
I understand that this rule is necessary to compute lowlink accordingly to its formal definition, which in Tarjan's paper is (emphasis is mine)
LOWLINK(v) is the smallest vertex which is in the same component as v and is reachable by traversing zero or more tree arcs followed by at most one [back edge] or [cross edge].
What I do not understand is :
- Would removing the emphasized restriction in the definition lead to a calculation with
v.lowlink := min(v.lowlink, w.lowlink)?
- Would removing the emphasized restriction lead to incorrect detection of a graph's SCCs (if so, I am looking for an example of such a graph) ? If not, would this modification guarantee that in a given SCC, all nodes ultimately have the same lowlink value (again, if not, I am looking for a counterexample) ?
I am currently at the following point (which might be wrong !) :
Let v and w be as in the code (exploring v's successors, w already on stack). v is on the stack too, and so is r, the root of v and w's SCC (in Tarjan's sense) (it is a common ancestor of v and w in the spanning tree).
For the proposed modification of the algorithm to yield a bad result, one needs to have w.lowlink < r.lowlink (this is the case where, by propagating the lowlink information back to r after finishing DFS, we will get an inconsistent value for r). For this to happen, w must have gotten its lowlink value from a vertex x discovered before r and belonging to a different SCC than r. But x needs to be in the stack when we were DFSing from w (if it were not the case, one would not have updated w.lowlink when reaching x because x is already discovered at that time). Since x is discovered before r, it is deeper in the stack than r, and thus it is still in the stack when we are DFSing from v. But then wouldn't all these nodes belong to the same SCC, rooted by x.lowlink ?