1
$\begingroup$

I have been reading a book called The Algorithm Design Manual by Steven Skiena and one of the topics discussed there is an algorithm to find all the articulation points in a graph.

In it, we first construct a DFS tree and store the following information for each vertex in the DFS tree:

  • The traversal order at which we visited the vertex
  • The highest reachable ancestor from the tree for each vertex

After constructing the tree, the author says one of the following conditions need to be satisfied for a vertex to be an articulation vertex:

  • If the root has more than 1 child, it is an articulation point
  • If we have an edge A -> B which is a bridge, then A is an articulation point
  • If we have an edge A -> B (A is parent of B) and the highest reachable node from B is A, then A is an articulation point.

I wrote a program to test this and it works on the graphs I tested it against:

// lo[] contains highest index
// pre[] contains traversal order
private void dfsFindArticulationPoints(int node, int parent) {
    if(pre[node] != 0) {
        lo[parent] = Math.min(lo[parent], pre[node]);
        return;
    }
    
    pre[node] = index;
    lo[node] = index;
    index++;

    int childCount = 0;
    for(int child: graph[node]) {
        if(pre[child] != 0)
            childCount++;
        if(child == parent)
            continue;
        dfsFindArticulationPoints(child, node);
        lo[node] = Math.min(lo[child], lo[node]);

        // Check case 2 and 3
        if(node != 0 && pre[node] <= lo[child])
            articulationPoints.add(node);
    }

    // Check case 1
    if(node == 0 && childCount > 1)
        articulationPoints.add(0);
}

My Question: I understand why those three conditions work. However how can I convince myself that those are the only three conditions to check?

Can somebody please prove to me that those are the only three conditions and there are no other conditions to check for?

$\endgroup$
4
  • $\begingroup$ Is it possible to have an articulation point $v$ for which none of the conditions hold? Try it out with pen and paper - you will either convince yourself or discover a new situation to be considered. $\endgroup$
    – Juho
    Jan 1, 2021 at 12:54
  • $\begingroup$ I have been trying to do that but I have not been able to come up with a proof myself hence this question. I guess I can give it some more time and thought but for now I do not know how to make progress with the proof. $\endgroup$
    – Arat254
    Jan 1, 2021 at 13:12
  • 1
    $\begingroup$ I really hope that the book contains a proof that this algorithm works. Otherwise, I suggest finding a different book. $\endgroup$ Jan 1, 2021 at 14:58
  • 1
    $\begingroup$ In that case, I'd suggest reading the original paper by Hopcroft and Tarjan ("Algorithm 447: Efficient algorithms for graph manipulation") on computing the biconnected components of a graph (which easily yields the articulation points as well). $\endgroup$ Jan 1, 2021 at 15:11

1 Answer 1

1
$\begingroup$

Here is the proof:

Given we have A -> B as an edge where A is not the root, let's assume A is an articulation point thats not the root. Removing it results in 2 subsets - the first containing the root and the second containing B.

For the subset containing B to be disjoint from the root if A is removed, B should not have a link to any node from root ... A that is it should not be able to reach a vertex higher than itself. This is possible only if:

  • A -> B is a bridge meaning the highest node reachable from B is itself
  • A is the only node B is connected to that is above it. This way if we remove A the highest node reachable from B is itself.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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