Fundamental Definitions

In graph theory, certain vertices and edges play a critical role in maintaining connectivity. This article explores four key concepts that help analyze network robustness.

Articulation Points (Cut Vertices)

An articulation point is a vertex whose removal (including all incident edges) increases the number of connceted components in the graph.

Bridges

A bridge is an edge whose removal disconnects the graph, splitting a connected component into two separate components.

Edge-Biconnected Components

An edge-biconnected component represents a maximal subgraph where no edge acts as a bridge. Within such a component, any two vertices remain connected even after removing any single edge.

Vertex-Biconnected Components

A vertex-biconnected component is a maximal subgraph that remains connected after removing any single vertex (and its incident edges). Unlike edge-biconnected components, these may share articulation points between them.

Algorithmic Approach Using Tarjan's Method

All four concepts can be efficiently identified using Tarjan's depth-first search algorithm, which tracks discovery times and low-link values for each vertex.

Identifying Articulation Points

The algorithm traverses the DFS tree, maintaining two key arrays:

• discovery[v]: The timestamp when vertex v is first visited
• lowlink[v]: The smallest discovery time reachable from v through zero or more tree edges followed by at most one back edge

The crucial insight: For a vertex u with child v in the DFS tree, if lowlink[v] >= discovery[u], then u is an articulation point. This condition indicates that v cannot reach any ancestor of u without passing through u itself.

Special handling applies to the root node: it becomes an articulation point only if it has at least two children in the DFS tree.

void findArticulation(int node, int parent) {
    discovery[node] = lowlink[node] = ++currentTimestamp;
    int childCount = 0;
    
    for (int neighbor : adjacency[node]) {
        if (discovery[neighbor] == 0) {
            childCount++;
            findArticulation(neighbor, node);
            lowlink[node] = min(lowlink[node], lowlink[neighbor]);
            
            if (parent != -1 && lowlink[neighbor] >= discovery[node]) {
                isArticulation[node] = true;
            }
        } else if (neighbor != parent) {
            lowlink[node] = min(lowlink[node], discovery[neighbor]);
        }
    }
    
    if (parent == -1 && childCount >= 2) {
        isArticulation[node] = true;
    }
}

Finding Bridges

The bridge detection algorithm follows a similar pattern. An edge (u, v) is a bridge if and only if lowlink[v] > discovery[u], meaning vertex v cannot reach any ancestor of u through alternative paths.

struct Edge {
    int source, destination;
};

void detectBridges(int current, int parent) {
    discovery[current] = lowlink[current] = ++timer;
    
    for (int next : graph[current]) {
        if (next == parent) continue;
        
        if (discovery[next] == 0) {
            detectBridges(next, current);
            
            if (discovery[current] < lowlink[next]) {
                bridges.push_back({min(current, next), max(current, next)});
            }
            
            lowlink[current] = min(lowlink[current], lowlink[next]);
        } else {
            lowlink[current] = min(lowlink[current], discovery[next]);
        }
    }
}

Computing Edge-Biconnected Components

Edge-biconnected components can be extracted by modifying the standard Tarjan algorithm. When lowlink[u] == discovery[u], all vertices above u in the recursion stack form one component. The algorithm marks bridge edges during traversal and later groups vertices avoiding these edges.

void findEdgeBiconnected(int vertex, int parentEdge) {
    discovery[vertex] = lowlink[vertex] = ++timestamp;
    componentStack.push(vertex);
    
    for (auto &[to, edgeId] : connections[vertex]) {
        if (edgeId == parentEdge) continue;
        
        if (discovery[to] == 0) {
            findEdgeBiconnected(to, edgeId);
            lowlink[vertex] = min(lowlink[vertex], lowlink[to]);
            
            if (lowlink[to] > discovery[vertex]) {
                isBridgeEdge[edgeId] = true;
            }
        } else {
            lowlink[vertex] = min(lowlink[vertex], discovery[to]);
        }
    }
    
    if (lowlink[vertex] == discovery[vertex]) {
        componentCount++;
        while (true) {
            int member = componentStack.top();
            componentStack.pop();
            edgeBCC[componentCount].push_back(member);
            if (member == vertex) break;
        }
    }
}

Extracting Vertex-Biconnected Components

Vertex-biconnected components require more careful stack management. When encountering an articulation point condition (lowlink[v] >= discovery[u]), we pop vertices from the stack until v is reached, creating a new component that includes both the popped vertices and the articulation point u itself. The articulation point remains on the stack as it may belong to multiple comopnents.

void findVertexBiconnected(int node) {
    discovery[node] = lowlink[node] = ++timeCounter;
    dfsStack.push(node);
    
    if (node == root && adjacency[node].empty()) {
        componentId++;
        vertexBCC[componentId].push_back(node);
        return;
    }
    
    int childNodes = 0;
    for (int adjacent : adjacency[node]) {
        if (discovery[adjacent] == 0) {
            childNodes++;
            findVertexBiconnected(adjacent);
            lowlink[node] = min(lowlink[node], lowlink[adjacent]);
            
            if (lowlink[adjacent] >= discovery[node]) {
                if (node != root || childNodes > 1) {
                    isCutVertex[node] = true;
                }
                
                componentId++;
                int stackMember;
                do {
                    stackMember = dfsStack.top();
                    dfsStack.pop();
                    vertexBCC[componentId].push_back(stackMember);
                } while (stackMember != adjacent);
                vertexBCC[componentId].push_back(node);
            }
        } else {
            lowlink[node] = min(lowlink[node], discovery[adjacent]);
        }
    }
}