# Finding all nodes that are passed by all paths from A to B in an undirected graph

I searched all over internet but couldn't find any particular info on this one, so i thought to give it a shot here.

Problem: We have an undirected unweighted graph $G$, and in this graph we have two nodes $A$ and $B$. Now lets take the set of all paths between $A$ and $B$ and call that set $\mathcal{P}$, further note these paths can pass each node either once or dont pass a node at all. Of course one path $P \in \mathcal{P}$ exists out of both nodes and edges, so let $N(P)$ be the set of nodes associated with the path $P$. Now I would like to know in a fast algorithmical way which nodes are left if we take the the intersection between all vertices of all paths between $A$ and $B$, so more mathematically i want to know the set $\bigcap_{P \in \mathcal{P}} N(P)$.

Example:

The green nodes are traveling through all paths between $A$ and $B$, so they are the nodes i look for. the intersection between all pathnodes therefor is the set of all green nodes and $A$ and $B$ might be included in that set as well, depending on the algorithm.

-
A simpler way of writing this would be: "Find all nodes that lie on every simple path from $A$ to $B$". – Paresh Feb 15 '13 at 12:31
Oh yea, thanks, i already thought it might be a bit long of an explanation – CarloV Feb 15 '13 at 12:39

## 1 Answer

The vertices that you are looking for are all cut-vertices (or articulation points) of the graph. A cut vertex is a vertex that disconnects the graph/increases the number of connected components. However, not all cut-vertices are a solution. Any cut-vertex, whose removal causes $A$ and $B$ to become disconnected, will lie on every path from $A$ to $B$.

Edit: Another observation is that the desired vertices will lie on the shortest path from $A$ to $B$ (if they lie on any path from $A$ to $B$, then they also lie on the shortest path). You can find the shortest path in linear time using a BFS. Now, you can shortlist those vertices which are cut-vertices and lie on the shortest path from $A$ to $B$.

-
If you cut out the white vertex attached to $A$, we can still make paths to $B$, so would it be enough to first need to trim the appendixed or dead vertices and then search for these cut-vertices in the remaining graph? Anyhow at least i know the names for these nodes now, that makes it much easier. – CarloV Feb 15 '13 at 12:52
@CarloVerschoor The white vertex you mention is also a cut-vertex of the graph. But its removal does not disconnect $A$ and $B$, so it is not part of the answer. However, you can find all cut-vertices of the graph using one DFS in $O(|V| + |E|)$. From those, you can weed out those vertices whose removal still keeps $A$ and $B$ connected. This would result in a worst case $O(|V|^2 + |V||E|)$ algorithm. If I can think of something better, I'll update my answer. – Paresh Feb 15 '13 at 13:03