Articulation points (or cut vertices), but only subset of vertices need to be connected

Question

I know we can find all articulation points efficiently in a graph using DFS.

But what if not all nodes need to be connected, but instead we have set of node pairs that need to communicate (there is a path between them). How to efficiently find all nodes (vertices) which removal will cause at least one of the mentioned pairs to be disconnected (can't communicate with each other)?

For example, we can have different cases for image below (undirected graph):

1. If pairs are A-B and C-D, then 2 is not vertex cut, because pairs remain connected.
2. If pairs are A-C and B-D, then 2 is vertex cut, because pairs can't communicate (there is no path between them).

If we know set of pairs that need to communicate, what is the most efficient way to find all "vertices cuts"?

Answer 1

I believe this can be computed in linear time, as follows:

Compute the block-cut tree. This can be done in linear time.

Preprocess the tree so that you can answer least common ancestor queries in constant time.

Given a pair $u,v$ of vertices, find the biconnected components they are contained in, then find their least common ancestor in this tree, call it $a$. Now mark all tree nodes along the path from $u$ to $a$ and from $v$ to $a$ (excluding $u$ and $v$ themselves).

Run this algorithm for each pair.

Finally, output all cut vertices (articulation points) that are marked.

I suggest that you first sort the pairs $(u,v)$ by height of their lca $a$, so that you start first with the pairs whose lca is closest to the root, and then progress on to ones that are farther from the root. With this ordering, one can then apply the following optimization: when traversing upwards from $u$ to $a$, if you encounter a node in the tree that is already marked, you can stop the traversal early.

With these optimizations, the running time will be linear. You can compute the block-cut tree in linear time. You can also compute the least-common ancestor in constant time. Finally, the time to do the traversals will be linear in the number of nodes in the graph plus the number of pairs, since you visit each node at most once during the traversals (if it has been visited previously, you terminate that traversal).

Answer 2

Let $P$ be the set of pairs of vertices that need to communicate and let $n$ be the number of vertices of the graph.

Compute the block-cut tree $T$ of your graph and root it in an arbitrary vertex. Remove from $P$ all pairs that belong in the same block. For any vertex $v$ of the graph, let $b_v$ be the vertex of $T$ representing the block in which $v$ belongs.

For each of the surviving pairs $(u,v) \in P$, compute the lowest common ancestor $LCA(b_u, b_v)$ of $b_u$ and $b_v$ in $T$. This requires $O(n + |P|)$ time using, e.g., Tarjan's algorithm.

For every pair $(u,v) \in P$, the cut vertices that disconnect $u$ from $v$ are exactly those that appear in the (unique) path of $T$ from $b_u$ to $LCA(b_u, b_v)$ or in the (unique) path of $T$ from $b_v$ to $LCA(b_u, b_v)$.

These vertices can be found efficiently by visiting $T$ in postorder. While visiting a vertex $x$, keep track of a special vertex $s_x$. This vertex might not always exist, but if it does it will always be an ancestor of $x$. The meaning of $s_x$ is the following: all cut-vertices in the path from $x$ to $s_x$ disconnect at least one pair in $P$.

The visit of a generic vertex $x$ proceeds as follows:

• 1. Let $x_1, x_2, \dots$ be the children of $x$ in $T$, and set $s_x$ to the vertex of lowest depth in $T$ among $s_{x_1}, s_{x_2}, \dots$, if any.
• 2. If $x$ represents a block $B$:
     • 2.1. For each pair $(u,v) \in P$ such that $\{u,v\} \cap B \neq \emptyset$, set $s_x$ to the lowest vertex among $s_x$ itself (if $s_x$ exists) and $LCA(u,v)$.
• 3. If $x$ is a cut-vertex, $s_x$ exists, and $x$ is a descendant of $s_x$ (a vertex is a descendant of itself):
     • 3.1. Report $x$ as a cut-vertex disconnecting a pair of interest.

Step 1 requires time proportional to the number of children of $x$ in $T$, therefore the total time spent in this step will be $O(n)$. The overall time required to perform step 2 is $O(n+|P|)$ after a $O(|P|)$ preprocessing that associates the pairs in $P$ to the corresponding blocks. Finally, step 3. requires constant time per vertex (since the ancestor-descendant relation can be checked in constant time after a $O(n)$ preprocessing).