§ Articulation points

I find DFS fascinating, and honestly insane for how much structral information of the graph it manages to retain.
A vertex vv is an articulation point of a graph GG if the removal of vv disconnects the induced subgraph.

§ Tactic 1 - Inductively

We first solve the super easy case with the root, and then try to see if we can treat other cases like the root node case, then we're good. Here, we are given an graph GG, and we are thinking about a DFS tree TGT_G of the graph GG.

§ Thinking about the root

When is the root an articulation point? If the root has multiple children, then it is an articulation point; If we remove the root, then it disconnects the children. This is because we have an undirected graph, where we only have back edges, and no cross edges. A back edge can only go from a node to its ancestor. If we remove the root, the back edges cannot save us, for there is no ancestor higher than the root to act as an alternate path

§ Non root vertex

When is a non root vertex vv an articulation point? When there is some child ww of vv such that the subtree of ww cannot escape the subtree of vv. That is, all back edges from ww do not go above vv. If we were to now remove vv, then ww would be disconnected from the rest of the graph.
Alternate phrasing: When all cycles in the subtree of ww are within the subtree of vv. This means that the backedges cannot go above vv. If ww could build a cycle that goes above vv, then vv would not be an articulation point, because it'll be involved in some cycle vwpvv \mapsto w \mapsto \mapsto p \mapsto v, which gives us an alternative path to reach ww even if vv is removed.
One way to imagine this maybe to imagine vv as the new root, and the other stuff that's above vv to be to the left of ww. That way, if we could go to ww, we get a cross edge from the "new root"(v) and the "other section" (the part that's connected by a cross edge). If we prevent the existence of these "fake cross edges", we're golden, and vv is then an articulation point.

§ Tactic 2 - Structurally / Characterization

Next we follow a "mathematical" development, where we build theorems to characterize k-connectedness and use this to guide our algorithm design

§ Menger's theorem

Let GG be a connected undirected graph. Let u,vu, v be two non-adjacent vertices. The minimum number of vertices whose removal from GG disconnects uu and vv is equal to the maximal number of vertex disjoint paths from vv to uu.

§ Whitney's theorem (corollary)

An undirected graph is kk connected iff kk vertices must be removed to disconnect the graph.

§ Biconnected components

Menger's theorem tells us that a graph is not biconnected iff we can find a vertex whose removal disconnected the graph. Such a vertex is an articulation vertex.
A biconnected component is a maximal subset of edges, such that the induced subgraph is biconnected. Vertices can belong to many components; Indeeed, articulation vertices are those that belong to more than one component.

§ Lemma: Characterization of biconnected components

Two edges belong to the same biconnected component iff there is a cycle containing both of them. [This lemma is silent about biconnected components of single edges]
We show that a cycle is always contained in a single binconnected component. If a cycle contains edges from more than one biconnected component, then we can "fuse" the biconnected components together into a single, larger, biconnected component.

§ Lemma: Each edge belongs to exactly one biconnected component

§ Tactic 3 - 'Intuitively'

We look at pictures and try to figure out how to do this.

§ DFS for articulation vertices - undirected:

  • The connectivity of a graph is the smallest number of vertices that need tobe deleted to disconnect the graph.
  • If the graph has an articulation vertex, the connectivity is 1. More robustgraphs that don't have a single point of failure/articulation vertex aresaid to be binconnected.
  • To test for an articulation vertex by brute force, delete each vertex,and check if the graph has disconnected into components. this is O(V(V+E))O(V(V+E)) time.
Joke: an articulate vertex is one that speaks very well, and is thus important to the functioning of the graph. If it is killed, it will disconnect society, as there is no one to fulfil its ability to cross barriers with its eloquent speech.

§ Articulation vertices on the DFS tree - undirected

  • If we think of only the DFS tree for a moment of an undirected graph and ignore all other edges, thenall interneal non-leaf vertices become articulation vertices, because theydisconnect the graph into two parts: the part below them (for concreteness,think of a child leaf), and the root component.
  • Blowing up a leaf has no effect, since it does not connect two components, a leaf only connects itself to the main tree.
  • The root of the tree is special; If it has only one child, then it acts likea leaf, since the root connects itself to the only component. On the otherhand, if there are multiple components, then the root acts like an internalnode, holding these different components together, making the root anarticulation vertex.

§ Articulation vertices on the DFS graph - undireced

  • DFS of a general undirected graph also contains back edges. These act assecurity cables that link a vertex back to its ancestor. The securitycable from x to y ensures that none of the nodes on the path [x..y]can be articulation vertices.
  • So, to find articulation vertices, we need to see how far back the security cables go.
int anc[V]; int dfs_outdeg[V];
void processs_vertex_early(int v) { anc[v] = v; }
void process_edge(int x, int y) {
  if (dfsedge[x][y].type == TREE) { dfs_outdeg[x]++; }
  // y <-*
  //     |
  //     BACK
  //     |
  // x --*
  if (dfsedge[x][y].type == BACK && (parent[y] != x)) { 
     if(entry_time[y] < entry_time[anc[x]]) {
       anc[x] = y;
     }
  }
}
In a DFS tree, a vertex v (other than the root) is an articulation vertex iff v is not a leaf and some subtree of v has no back edge incident until a proper ancestor of v.

§ References