# 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 $1\leq i\leq 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|))$.

• Here is a thought: consider the color-adjacency matrix A_i, where (u,v)=1 iff u and v have a path using vertices only from at most i different partition classes, i running from 1 to n. Perhaps s and t have a path involving log(n) colors, and then the worst case for your shortest path algorithm would involve log(n) instead of n. You may get lucky and find an algorithm to compute, say, A_(2^j) quickly. Gerhard "Ask Me About System Design" Paseman, 2010.03.12 Mar 12, 2010 at 9:04
• Would A_i take $O(n^2)$ time to setup though?
– Opt
Mar 12, 2010 at 9:09
• It might. Even computing the row for vertex s might take some time. However, computing A_i for all pairs s,t might be useful in other applications. Gerhard "Ask Me About System Design" Paseman, 2010.03.12 Mar 13, 2010 at 7:55
• I am not sure if I get the point. Are there any restrictions on the components C_i? If there isn't any, then why not take all neighbors of s? Mar 22, 2010 at 12:37
• You want a list of all the C_i, that's why just taking the neighbors does not suffice.
– Opt
Mar 22, 2010 at 16:30

Consider the problem in which every "component" is a single vertex. Then the problem is to find every $s$-$t$ cutvertex in $O(|E|)$ time, which is fairly easy (each lies on every $s$-$t$ path).
If your components are not necessarily connected, it might be more difficult. You would have to solve the case in which each $C_i$ is an independent set.