3
$\begingroup$

Given undirected, connected graph, find all pairs of nodes (connected by an edge) whose deletion disconnects the graph. There can't be an edge connecting a node to itself.

The problem seems similar to finding articulation points of a connected, undirected graph - yet with a twist, that we have to remove a pair of vertices connected by an edge (and all other edges connected to that pair).

This is a homework question. I might not be a smart student, but neither a lazy one. I will try to answer it below, and I would love for someone to verify my understanding of the issue.

I will be basing my solution of finding Articulation Pairs (AP) based on finding articulation points by this analysis: https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ and the DFS with additional bookkeaping of 'lowpoint' value for each node, where
lowpoint(v) is a minimal depth of non-parent adjecent node at the time of traversal
found here: https://en.wikipedia.org/wiki/Biconnected_component#Algorithms

Analysis:
1) u is root of DFS tree with at least three children. Then every pair (u, child(u)) is AP.
2) u is root with at least two children, one of which (v) has at least one child. Then every pair (u, v) is AP.
3) u is not a root of DFS tree and it has a child v1 such that v1 has child v2, such that no vertex in subtree rooted with v2 has a back edge to one of the ancestors of u

Rephrasing 3):
(u,v) is AP iff:
- v is a child of u
- there exist child(v) such that lowpoint(child(v)) >= depth(u)

My questions are:
Did I miss any case? Is my reformulation of the issue sufficient for this problem?

@EDIT: This solution/analysis completely doesn't work and at this point I have no idea how to approach this issue.

$\endgroup$
  • $\begingroup$ Such an edge is called "bridge" (or "isthmus", "cut-edge"). www.geeksforgeeks.org has a separate page for this problem. As you observe, the general approach is that of articulation-points. I did not verify your conclusions. $\endgroup$ – Hendrik Jan Jun 3 '18 at 23:20
  • $\begingroup$ This is not a bridge problem, unfortunately. $\endgroup$ – MkjG Jun 3 '18 at 23:50
  • 1
    $\begingroup$ @HendrikJan We remove not only a single edge, but two vertices -> this means an edge between them, but also every other edge connected to each of thoes vertices. $\endgroup$ – MkjG Jun 3 '18 at 23:50
  • 1
    $\begingroup$ @HendrikJan Specifically, a graph represented by a circle with a single diameter line can be disconnected by removing 'diameter'-edge and two vertices connected to it. It seems like lowpoint analysis is useless in this case (all vertices in such graph would have lowpoint of zero). $\endgroup$ – MkjG Jun 4 '18 at 2:07

Your Answer

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

Browse other questions tagged or ask your own question.