Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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 –  Gerhard Paseman Mar 12 '10 at 9:04
    
Would A_i take $O(n^2)$ time to setup though? –  Opt Mar 12 '10 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 –  Gerhard Paseman Mar 13 '10 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? –  Sangxia Huang Mar 22 '10 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 '10 at 16:30

1 Answer 1

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

You can use this to solve your problem in the case where each "component" is a connected component -- I'm not sure if you meant to specify this in the first place -- by contracting each component down to a single vertex à la graph minors and solving the case where every component is a single vertex.

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.

share|improve this answer
    
at least as stated, it sounds like the C_i could be disconnected. –  Suresh Venkat Mar 13 '10 at 8:09
    
Yeah, each "component" here which is really a set of vertices may not be connected, i.e. if all components except for the one in consideration were removed, then the component would become disconnected. –  Opt Mar 22 '10 at 16:33

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.