3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ Mar 12, 2010 at 9:04
  • $\begingroup$ Would A_i take $O(n^2)$ time to setup though? $\endgroup$
    – Opt
    Mar 12, 2010 at 9:09
  • $\begingroup$ 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 $\endgroup$ Mar 13, 2010 at 7:55
  • $\begingroup$ 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? $\endgroup$ Mar 22, 2010 at 12:37
  • $\begingroup$ You want a list of all the C_i, that's why just taking the neighbors does not suffice. $\endgroup$
    – Opt
    Mar 22, 2010 at 16:30

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ at least as stated, it sounds like the C_i could be disconnected. $\endgroup$ Mar 13, 2010 at 8:09
  • $\begingroup$ 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. $\endgroup$
    – Opt
    Mar 22, 2010 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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