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