I'm working on the following problem:
Given an undirected graph G = (V, E), represented as an adjacency list, design an efficient algorithm to construct a subgraph H = (V, E') such that:
E' is a subset of E
H is connected
H is bridgeless (i.e., for every edge e in E', removing e keeps H
connected)
The number of edges in H is at most 2V (i.e., |E'| ≤ 2 * |V|)
So far, here's what I've done and understood:
I'm using Tarjan's algorithm to find all bridges in the graph.
I run a depth-first search to check if the graph is connected and has no bridges. If it's disconnected or has bridges, then there's no valid solution.
Assuming the graph is connected and bridgeless, I construct a spanning tree T of G.
This is where I'm stuck:
I want to add some of the non-tree edges from G to T to obtain a new graph H that:
I'm not sure how to choose which non-tree edges to add to ensure the final graph is bridgeless and satisfies the edge constraint.
Any ideas or pointers on how to do this efficiently?
Thanks in advance!
First, make your spanning tree with DFS, also labeling each vertex with its depth in the DFS tree. This takes linear time and uses |V|-1 edges, and the DFS tree has the useful property that all unused edges connect a vertex to one of its ancestors.
For each vertex in the DFS tree, except the root, add the one unused edge, if any, that connects it to its shallowest/farthest ancestor. Note that any other unused edges on the vertex are redundant in terms of preventing bridges, because their vertices will be on the cycle you just created. This can again be done in linear time and again uses at most |V|-1 edges.
All together, then, this takes linear time and uses at most 2|V|-2 vertices. Any graph edges that have been left out have been proven unnecessary, so the resulting graph is bridgeless iff the original one is. It's pretty easy to do the whole algorithm in one DFS pass if you like, and also easy to detect bridges at the same time.