A back-edge is an edge that connects a node to one of its ancestors in a DFS tree. For example, in the above diagram, vertex 6 is the root and during DFS, vertex 2 points back to vertex 6, this edge (2 → 6) is a back-edge. Similarly, an edge from node 4 to node 5 (4 → 5) is also a back-edge as node 5 is an ancestor of node 4.

Is an Edge to the Immediate Parent Considered a Back-Edge?

Yes, an edge from a child node to its immediate parent is technically a back-edge, but for finding articulation points, such edges are not considered. This is because when a node is removed, its direct connection to its parent does not exist in the modified graph.

Efficiently Finding Back-Edges

To efficiently determine if a node is an articulation point, we use two arrays:

• discovery_time[]: This array keeps track of the time at which each node is first visited during the DFS traversal. The "time" here represents the order in which nodes are visited.
• low[]: This array stores the earliest (smallest) discovery time that can be reached from a given node using any combination of its own edges and back-edges.

How to Update the low[] Array

1. For a Tree Edge (an edge from a parent to a child in the DFS tree):

   • When visiting a child node from its parent during DFS, update the low value of the parent node by taking the minimum of its current low value and the low value of its child. This update ensures that the parent node is aware of any back-edges reachable through its children.
   • Update Rule:
     low[node] = min(low[node], low[child_node])

2. For a Back-Edge (an edge that points back to an ancestor of the current node):

   • When a back-edge is found (a child points to an ancestor of the current node, excluding its direct parent), update the low value of the current node to be the minimum of its current low value and the discovery_time of the node that the back-edge points to. This captures the earliest reachable ancestor node using the back-edge.
   • Update Rule:
     low[node] = min(low[node], discovery_time[child_node])

Condition to Identify an Articulation Point

A non-root node U is an articulation point if there exists at least one child V such that:

• Condition: low[V] >= discovery_time[U]

This condition means that there is no back-edge from any node in the subtree rooted at V to any ancestor of U. If this is true, removing U would separate V (and its subtree) from the rest of the graph, making U a critical connection point or articulation point.

Step-by-Step Algorithm for Case 2

1. Initialize Discovery and Low Arrays:

   • Set all entries in discovery_time and low arrays to -1.

2. Set Discovery and Low Time for Current Node:

   • For the current node, set discovery_time[current_node] and low[current_node] to the current DFS time.

3. Increment Time for the Next Node Visit:

   • Increment the DFS time by 1.

4. Traverse Each Child Node:

   • For every child of the current node:
     • If the child has not been visited:
       • Perform a DFS on the child.
       • Update low[current_node] to the minimum of low[current_node] and low[child].
       • Check if current_node is not the root and low[child] >= discovery_time[current_node].
       • If true, mark current_node as an articulation point.

5. Handle Back-Edges:

   • If the edge is a back-edge (child is not a parent), update low[current_node] with discovery_time[child].

Pseudocode for Case 2

// Initialize discovery_time and low arrays with -1

void dfsForNonRootArticulation(int currentNode, vector<int>& discovery_time, vector<int>& low, int parent, int time) {
    // Step 2: Set discovery and low time for the current node
    discovery_time[currentNode] = low[currentNode] = time;
    time++; // Step 3: Increment the DFS time

    // Step 4: Traverse each child of the current node
    for each (adjacentNode of currentNode) {
        if (discovery_time[adjacentNode] == -1) { // If the child is not visited
            dfsForNonRootArticulation(adjacentNode, discovery_time, low, currentNode, time);

            // Update low value for the current node
            low[currentNode] = min(low[currentNode], low[adjacentNode]);

            // Check if the current node is an articulation point
            if (parent != -1 && low[adjacentNode] >= discovery_time[currentNode]) {
                markArticulationPoint(currentNode); // Mark as articulation point
            }
        }
        // Step 5: Handle back-edge, ignore edge to parent
        else if (adjacentNode != parent) {
            low[currentNode] = min(low[currentNode], discovery_time[adjacentNode]);
        }
    }
}