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 any of 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"?

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"?

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 some of 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"?

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 any of 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"?