Find all edges in a graph which if removed, would disconnect a pair of vertices

Question

I have an undirected graph G(V, E). The problem I am trying to solve is broken down into two parts:

Part 1: Given the graph, and a pair of vertices in the graph, find the edges which are contained in all paths between this pair of nodes.

Part 2: Given the graph, find all such edges such that each one is present along all paths between any two vertices in the graph.

An example for Part 2: Let the graph have nodes {a, b, c, d, e, f, g}. Let edges be:

{a, b},
{b, c},
{c, a},
{c, d},
{d, e},
{e, f}
{f, g},
{g, e}

For this graph, {c, d} and {d, e} should be the edges returned.

How can you do it efficiently?

Seems like a homework assignment. What have you tried so far? You've shown no work. — David Makogon
It's far from a homework assignment. I am trying to solve this as part of my job. :) The only thing that comes to mind for me is to enumerate all paths and find intersection between them for all pairs of vertices. But unfortunately it is NP complete. — Diptesh Chatterjee
Part 2, as formulated, will give no edges for a non-trivial graph. You'd need to consider only pairs of vertices that are in different 2-connected components — voidengine

Matt Timmermans Matt Timmermans · Accepted Answer · 2017-03-03T05:37:29

If an edge E is on a path from vertex A to vertex B, but there is also a path from A to B that does not include E, then then E is in a cycle.

If E is in a cycle, and E is on a path from A to B, then there is a path from A to B through the other edges in the cycle that does not include E.

So, the edges you are looking for in part 2 are the edges that are not in cycles that are also on a path from A to B.

To answer your questions then:

1) Use the Hopcroft/Tarjan algorithm to find all the biconnected components (cycles) in the graph. See https://en.wikipedia.org/wiki/Biconnected_component

2) Collapse each biconnected component to a single vertex (more precisely, combine any 2 vertexes connected by an edge that is in a cycle until you run out of such edges). This will create a tree corresponding to the block cut tree (also described in the above link). The component that includes A will be A in the new graph, and similarly for B.

3) Since the resulting graph is a tree, it will have only one path from A to B. Find it with DFS. The edges on that path are the answer to part 2.

4) The edges from (3), as well as the edges in every biconnected component that is adjacent to those edges, are the answer to part 1.

Yeah, it kinda sounds like @EmmanuelAC's answer was trying to point in this direction.

Find all edges in a graph which if removed, would disconnect a pair of vertices

2 Answers