Tarjan's SCC : example showing necessity of lowlink definition and calculation rule?

Question

Several questions (1, 2) have been asked about this topic already but I am trying to be more specific.

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 :

1. Would removing the emphasized restriction in the definition lead to a calculation with v.lowlink := min(v.lowlink, w.lowlink) ?
2. 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 ?

Answer 1

For a given vertex, the only thing that matters in the algorithm is if there is an edge from the vertex or a child-vertex to a ancestor-vertex in the DFS exploration tree. In this case, we know that the vertex belongs to the same SCC as it's parent. In such a case, we are sure that the vertex itself or a child-vertex has a direct back edge to an ancestor of the vertex, and this ancestor has a lower index that the current vertex, so the v.lowlink will differ from v.index. We actually do not need to know the top-vertex of the SCC at this step.

So, using v.lowlink := min(v.lowlink, w.lowlink) instead of v.lowlink := min(v.lowlink, w.index) will lead to a correct algorithm too. The difference is that in this case, v.lowlink will not represent the vertex with the smallest id reachable from v nor the SCC top vertex, but just v if there is no such vertices, or any parent vertex that belongs to the same SCC (maybe the top-vertex), depending of DFS order. I think it's just lack in formal definition, and thus, wasn't used.

Let's see what appends when we use this alternative instruction. When we update v.lowlink because we have found a new back edge to a ancestor vertex, we will now set v.lowlink with the value of w.lowlink. But this vertex is an ancestor and is still in the stack: we may not have already explored all the child vertices of this ancestor and thus, w.lowlink can change in the future: this is why we dont's know exactly what will be the final value of v.lowlink because it depends of the DFS order. We can juste be sur that it will be w.index or a vertex with a lower index that belongs to the same SCC (so the algorithm will work as expected): the value of lowlink still differs for differents vertices of the same SCC.

The following example show how DFS order alters lowlink values in this alternative algorithm: In this case, assuming we are exploring vertices in the order 0-1-2-3-4, when we consider the vertex 3, the vertex 4 has not been explored yet. The lowlink value of vertex 1 is so 1, and vertices 2 and 3 will take the same value. But we will later find the back edge from 4 to 0, and set the lowlink value of vertices 4 and 1 at 0. If we had explored vertex 4 prior to vertex 2, all vertices would have 0 as lowlink value.

And for the last question, yes, all this verteces belong to the same SCC, rooted by x.lowlink or an ancestor of the vertex with id x.lowlink