2
$\begingroup$

Suppose that we have an undirected graph, and that for any two nodes there is a path from one to another. In such a graph, there might be some nodes that, if removed from the graph individually, leave behind the starting graph as two or more subgraphs - that is, removing one of the said nodes no longer makes possible to find a path between any two nodes.

What I want is a good algorithm to find how many these nodes are - nodes that if removed individually tear the graph connectivity apart.

What I have thought so far involves removing a node at the time and trying to reach all nodes from a starting node - failing to reach every node would mean the node removed is of the kind I am looking for. Some optimizations may apply, but that's the main idea.

Can you propose any better algorithm for this, e.g. taking advantage of say the degree of the nodes?

EDIT: After having found the answer, my question is equal to asking to find the number of articulation points in an undirected graph, so the title has changed accordingly.

$\endgroup$
  • 2
    $\begingroup$ Google for vertex connectivity and Menger's Theorem. $\endgroup$ – Juho Nov 11 '16 at 20:20
2
$\begingroup$

After some searching, I came across exactly what I wanted - seems like knowledge of terms is important. Source from Wikipedia - Biconnected components.

Linear time depth first search

The classic sequential algorithm for computing biconnected components in a connected undirected graph is due to John Hopcroft and Robert Tarjan (1973).[1] It runs in linear time, and is based on depth-first search. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms (both 2nd and 3rd editions).

The idea is to run a depth-first search while maintaining the following information:

the depth of each vertex in the depth-first-search tree (once it gets visited), and for each vertex v, the lowest depth of neighbors of all descendants of v in the depth-first-search tree, called the lowpoint.

The depth is standard to maintain during a depth-first search. The lowpoint of v can be computed after visiting all descendants of v (i.e., just before v gets popped off the depth-first-search stack) as the minimum of the depth of v, the depth of all neighbors of v (other than the parent of v in the depth-first-search tree) and the lowpoint of all children of v in the depth-first-search tree.

The key fact is that a nonroot vertex v is a cut vertex (or articulation point) separating two biconnected components if and only if there is a child y of v such that lowpoint(y) ≥ depth(v). This property can be tested once the depth-first search returned from every child of v (i.e., just before v gets popped off the depth-first-search stack), and if true, v separates the graph into different biconnected components. This can be represented by computing one biconnected component out of every such y (a component which contains y will contain the subtree of y, plus v), and then erasing the subtree of y from the tree.

The root vertex must be handled separately: it is a cut vertex if and only if it has at least two INDEPENDENT (non-connectible) children. However, since we hold the child count of each visited node, and the count only increments if the adjacent node being checked is not already visited, the root having >=2 children count would surely mean that at least two of the root's children are independent. If there were no 2 independent children of the root, all of the children of the root apart from the first checked would be marked as visited BEFORE the DFS search returned to root and continued the search to the second child, therefore the root's children count would be stuck at 1.

The code below prints the said articulation points, but with minimal changes it can also just print out the count of the said points.

Pseudocode

GetArticulationPoints(i, d)
      visited[i] = true
      depth[i] = d
      low[i] = d
      childCount = 0
      isArticulation = false
      for each ni in adj[i]
          if not visited[ni]
              parent[ni] = i
              GetArticulationPoints(ni, d + 1)
              childCount = childCount + 1
              if low[ni] >= depth[i]
                  isArticulation = true
              low[i] = Min(low[i], low[ni])
          else if ni <> parent[i]
              low[i] = Min(low[i], depth[ni])
      if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)
          Output i as articulation point
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.