Sunday 15 April 2007

algorithms - Effect on connectivity when partitioning a graph

I have a connected graph $G=(V,E)$, $V$ being the vertex set and $E$ being the edge set. I partition the graph into components $C={C_1,dots,C_n}$ such that all $C_i$ are pairwise disjoint.



Take two vertices $s,t in V$ such that $s,t$ are connected by a path. Is there an $O(|V|+|E|)$ algorithm to find out the list of all $C_i in C$ such that if we remove the vertices in $C_i$ from the graph, then $s$ will become disconnected from $t$.



I know there is the $O(|C|(|V|+|E|))$ algorithm to do so by removing vertices in $C_i in C$ from the graph for all $1leq ileq n$ and then checking if $s$ and $t$ are connected.
This can be somewhat improved if we take all edge weights as 1 and compute the shortest path and then consider only components whose vertices are present in the shortest path but this still has worst case complexity $O(|C|(|V|+|E|))$.

No comments:

Post a Comment