1
$\begingroup$

An assignment question asks,

Given a connected, undirected graph $G$, describe an algorithm which can determine if the removal of any pair of vertices would cause $G$ to become disconnected.

There is an obvious brute force solution, which is to just generate all pairs of vertices, produce new graphs with those vertices removed, and then test if that graph is connected using something like a BFS, running in $O(|V|^3)$ time.

However, I feel like this is not the intent of the question. We learned about an algorithm to find the articulation points of a graph, and it seems like something like this should be possible to determine if the removal of any pair of vertices would disconnect the graph, but I am not sure how it would be applicable.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ The approach you describe requires $O(|V|^2 \cdot |E|)$ time, if $G=(V,E)$. Is finding the articulation points on $G$ and on $G - v$ for every $v \in V$ fast enough for you? $\endgroup$ – Steven Mar 31 at 1:32
  • $\begingroup$ That sounds plausible, but I wonder if there is a solution that does not require copying/modifying the graph. $\endgroup$ – user118555 Mar 31 at 1:34
  • $\begingroup$ Even if you are logically "modifying" the graph, in practice this boils down to ignoring $v$ when you perform the DFS visit of $G$ to compute the articulation points. No copying required. $\endgroup$ – Steven Mar 31 at 1:39
  • $\begingroup$ Okay, then I think that is probably the intended solution. I'll mark it as the answer if you post it. $\endgroup$ – user118555 Mar 31 at 1:40
1
$\begingroup$

Assume that $G=(V,E)$ does contain any articulation point (otherwise the answer is easy).

One simple approach that requires $O(|V| \cdot |E|)$ time is that of computing the articulation points of $G-v$ for each $v \in V$.

If you find any articulation point $u$ then removing the two of vertices $\{u,v\}$ disconnects the graph.

In practice this amounts to running the depth first search needed to compute the articulation points of $G-v$ on $G$, while ignoring the edges to $v$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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