Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

enter image description here

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.

share|improve this question
    
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
add comment

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$.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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