Indian Computing Olympiad

Training Material


Advanced graph algorithms

Articulation points

We are given a network of roads, where the roads have been relaid but work still has to be done at the intersections. Relaying an intersection will prevent traffic from flowing through that intersection. An intersection is critical if blocking that intersection disconnects two points. We want to avoid relaying a critical intersection during the day time.

Example 1:

                 a---------b
                 | \       |
                 |   \     |    e------------g
                 |     \   |  /  \         /   \
                 |       \ | /     \      /     \
                 c-------- d -------f    h-------i

Here, {d,e,g} are critical intersections.

Example 2:

                 a---------f--------g
                 |       / | \      |
                 |     /   |   \    |
                 |   /     |     \  |
                 | /       |       \|
                 b-------- d        h
                 | \
                 |   \
                 c--- d
      

Here {b,f} are critical intersections.

How do we identify critical intersections?

Naive solution:

Delete each intersection and do a bfs/dfs to check if the graph remains connected. This takes time O(MN).

Critical intersections are vertices that disconnect the graph if they are deleted. These are called "articulation points" or "cut vertices".

Articulation points can be identified in a single dfs.

The root of the dfs tree is an articulation point iff it has more than one child. If there are two children, there cannot be an edge from one subtree to the other, because non-tree edges are back edges and can only go to an ancestor.

When is a non-root vertex v an articulation point? Can we generalize the argument for the root?

When there is a child w of v in the subtree such that the highest vertex that w can reach by going forward along DFS edges and then taking *one* back edge lies at or below v. In other words, if v is removed, w and all vertices below w become disconnected. An alternative way of saying this is that we want to look for a child w of v such that there are no back edges from the subtree rooted at w that go strictly above v.

Let us construct a dfs tree rooted at a for the examples above. For each vertex, we have written its dfs number. Back edges are shown by ... edges.

Example 1:

                     ......... a-1
                    .  .     /
                    .  .   b-2
                    .  . /
                    .  d-3
                    ./ . \
                  4-c  .  e-5
                       ./  \
                     6-f     g-7
                             . \
                             .   h-8
                             . /
                             i-9
      

Here, d is an articulation point because it has a child e that satisfies the criterion above. Similarly, e is an articuation point (child g satisfies criterion) and so is g (child h satisfies the criterion).

Example 2:

                          b-1........
                        / ..  \       .
                      /  . .    \      .
                   c-2  .  .      e-4  .
                    |  .   .       |   .
                    | .    .       |  .
                   d-3     .      f-5 ......
                           .     /   \      .
                            .   /     \      .
                            a-6        g-7   .
                                        |    .
                                        |   .
                                       h-8 .

      

Here, b is an articulation point because it is the root and it has more than one child. f is an articulation point because it has a child g that satisfies this criterion.

For a node v, let low(v) denote the lowest indexed vertex reachable from v, via a sequence of 0 or more tree edges followed by a single back edge. This can be computed recursively as follows:

low(v) = min(

{low(u) for all children u of v},
smallest indexed node reachable directly a back edge from v)

To check if v is an articulation point:

For each child u of v, check if low(u) ≥ DFS_number(v).

If there is at least one child for which this happens, then that child's subtree will get disconnected if u is removed, so u is an articulation point.

From this it follows that v is an articulation point if

    max low(u) ≥ DFS_number(v)
    u in child(v)

Let us call this quantity maxlow(v).

Computing low(u) and maxlow(u) can be built in to DFS.

   count = 1;

   DFS(u)
   {
     visited[u] = true;

     DFS_number[u] = count; count++;  /* Assign unique
                                         DFS number to node */
     low[u] = u;

     for each edge (u,v) {

       if (visited[v]){

         if (v != parent[u]){                 /* Take min with back  */
           low[u] = min(low[u],DFS_number(v));/* edges from u.  Note */
         }                                    /* that (u,parent(u))  */
                                              /* is not a back edge  */

       }else{

         parent[v] = u;                      /* Set parent */

         DFS(v);                             /* Recursively
                                               check children */
         /* At this point, if low[v] ≥ low[u], report that u is
            an articulation point */

         low[u] = min(low[u],low[v]);

         maxlow[u] = max(maxlow[u],low[v]);
       }
     }
     return;
   }