Why Articulations Point or Cut Vertex in a Graph is sexy

Coding Sep 01, 2019

Introduction

A graph is a data structure represented by a set of vertices and edges G = (V, E). A vertex in a graph is called an articulation point or a cut vertex iff removing it disconnects the graph. It identifies the vulnerabilities in a connected network, on failure would split the graph. They are useful for designing reliable networks. Following are examples of the articulation point highlighted in red.

Articulation Point highlighted in red

Interesting Fact
Jeffery Westbrook and Robert Tarjan developed an efficient data structure for this problem. Tarjan is known for his pioneering work on graph theory algorithms and data structures (least common ancestors algorithm and strongly connected components algorithm)

Depth-first Search and Classification of Edges

The idea is to use DFS (depth-first search), it suggests to traverse more in-depth into the graph whenever possible.

Depth-First-Search

Another attractive property of the depth-first search is that the search can be used to classify the edges of the input graph G = (V, E).

  1. Tree edges would be those edges (u, v) if 'v' were first discovered by exploring edge (u, v).
  2. Forward edges are those nontree edges (u, v) connecting a vertex 'u' to a descendant v in a depth-first tree.
  3. Back edges are those edges (u, v) connecting a vertex 'u' to an ancestor v in a
    depth-first tree. Self-loops, which may occur in directed graphs, are considered
    to be back edges.
  4. Cross edges are all other edges. They can go between vertices in the same
    depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.

Tree_edges

Below image discusses the progress of the depth-first-search algorithm DFS on a directed graph. As the algorithm explores edges, they are shown as either shaded (if they are tree edges) or dashed (otherwise). Nontree edges are labelled B, C, or F according to whether they are back, cross, or forward edges. We timestamped the Vertices by discovery time/finishing time.

2019-08-31-20_06_34-MIT.Press.Introduction.to.Algorithms.2nd.Edition.eBook-LinG

Algorithm

The idea is to identify the articulation point using the classification of edges using DFS.

We use below stores to identify the articulation points
V -> store the visited element
D -> stores the discovery times of visited vertices
L - store the low times of each node
P -> stores parent vertices in DFS tree
Ap -> stores the articulation points

A vertex u is an articulation point if
1. u is the root of the tree, and it has at least two children
(removing root result in disconnected graph and consider root denotes the start of the DFS)

Approach
maintain a parent array P for vertices
P -> stores parent vertices in DFS tree
Condition in the code
if( P[u] == null && children > 1)

2. u is not the root of the tree, and it has a child v such that there is no back edge from v to one of the ancestors of 'u'
(the v child not reached from any ancestor of u)

Approach
maintain a discovery array D to store the discovery times of the vertices and maintain an array to store the low times of each node to identify the earliest visited vertex (the low time is initialized the same way as D and gets updated if any ancestor exists with lower low time)

D -> stores the discovery times of visited vertices
L - a map to store the low times of each node

Calculation to update the low time
L[u] = Math.Min(D[u], D[w])
where w is an ancestor of 'u' and there is a back edge from some descendant of u to w

Condition in the code
if( P[u] != null && L[u] >= D[u])

Pseudo Code

FindArticulationPoint(Graph graph) {
    // Initialize list of Visited, Discovery, Low time, 
    // Parent and Articulation Points
    Initialize V, D, L, P, Ap
    
    // set first vertex
    Let v = graph.FirstVertex();
    
    // mark initial discovery time
    Let t = 0;

    // Perform Depth-first search and populate Ap Articulation points
    Dfs(V, Ap, v, D, L, P, t);
    
    return Ap;
}

Dfs(V, Ap, v, D, L, P, t) {
    // Mark visited
    V.Add(v)
    // add discovery time and low time
    D.Add(t)
    L.Add(t)
    t++;
    
    Let children = 0
    Let isAp = false
    
    foreach(adjV in v.getAdjacentVertices) {

        // ignore if adjacent vertex is the parent (already visited)
        if(adjV == P[v]) {
            continue;
        }
        
        // if not already visited, visit it
        if(!V[adjV]) {
            P[adjV] = v;
            children++;
            // Dfs on adjacent vertex
            Dfs(V, Ap, adjV, D, L, P, t);
            
            // update isAp if low time of adjacent vertex is 
            // greater than the discovery time of the vertex
            if(L[adjV] >= D[v]) {
                // denotes that no ancestor or backedge to already visit
                isAp = true;
            } else {
                // update the low time
                L[v] = Math.Min(L[v], L[adjV]);
            }
        }  // if adjacent vertex is already visited
        else {
            // if adjacent vertex already visited, update the low time if required
            L[v] = Math.Min(L[v], L[adjV]);
        }
    }
    
    //checks if either conditions is yes, it is articulation point
    // condition 1 - root of the tree and atleast two children or
    // condition 2 - not the root and no backedge to ancestor
    if((P[v] == null && children >= 2) || P[v] != null && isAp ) {
        Ap.Add(v);
    }
    
}

Demo

TarjanAPDemoDepth

References