Definition of a reachable ancestor (Skiena TADM 2nd ed section 5.9.2)

Question

In The Algorithm Design Manual section 5.9.2, covering graphs and articulation vertices, Steven Skiena writes

Let reachable_ancestor[v] denote the earliest reachable ancestor of vertex v, meaning the oldest ancestor of v that we can reach by a combination of tree edges and back edges.

This phrasing is ambiguous. On the errata page of his website, he clarifies:

it is clearer to say: "denote the earliest reachable ancestor of vertex v, meaning the oldest ancestor of v that we can reach from a descendant of $v$ by using a back edge."

But to me, this phrasing is still somewhat ambiguous. Consider the following four-vertex graph G:

    A
    |
+ - B
|   |
|   C
|   |
+ - D

We conduct an alphabetical depth-first search (DB is a back edge). According to Skiena's revised definition, it would seem that A is a reachable ancestor of C as follows: D is a descendent of C, and we can reach A from D using a back edge by following the path DBA. However, execution of Skiena's code for finding articulation vertices via depth-first search on G results in reachable_ancestor[C] = B, not A; therefore I don't think he intends for A to count as a reachable ancestor of C.

Might it be more accurate to say that reachable_ancestor is the oldest ancestor of v that we can reach from a descendant of v by using a back edge but without passing through any other ancestors of v?

Answer 1

It seems that the term reachable is used in a rather confusing way. In general conception of graph theorists, reachable means that there is a path between two vertices; however, in this context, reachable means that there is a back-edge from a vertex in the subtree to one of the ancestors. The existence of such back-edge promises a loop that is free of any articulation vertex.

In my opinion, the use of reachable violates the general understanding of connectivity in graph theory. Therefore, Skienna must have revised this in a different way, using the right terminology.

Your reasoning is correct. I suggest you look at the algorithm in "Introduction to Algorithms", which have used "visit_time" instead.

Answer 2

A small modification makes the definition agree with Skiena's algorithm. "Let reachable_ancestor[v] denote the earliest reachable ancestor of vertex v, meaning the oldest ancestor of v that we can reach from a descendant of v by using at most one back edge."

If we view undirected edges as "two-way" directed edges, then to reach A from C would require two back edges: DB and BA. Thus the earliest ancestor that can be reached from C by using at most one back edge is B.