Algo: Tarjan's Bridge-Finding Algorithm

In any connected system—from a computer network to a transportation grid—some connections are more critical than others. A bridge is an edge in an undirected graph whose removal increases the number of connected components. Identifying these fragile links is vital for assessing reliability and planning redundancy. Tarjan's bridge-finding algorithm provides an elegant and efficient $O(V+E)$ solution by performing a single Depth-First Search (DFS), cleverly tracking timing information to pinpoint exactly which edges are indispensable.

Foundations: DFS and the Concept of a Bridge

To understand Tarjan's algorithm, you must first be comfortable with Depth-First Search (DFS) traversal on an undirected graph. DFS explores a graph by proceeding as far as possible along a branch before backtracking, creating a DFS spanning tree. The edges used to discover new vertices become tree edges. Crucially, any edge connecting a vertex to an already-visited ancestor in the DFS tree (that is not its direct parent) is a back edge. Back edges create cycles, and this property is key to bridge detection.

A bridge is fundamentally an edge that is not part of any cycle. If an edge lies on a cycle, there exists an alternative path between its endpoints, so its removal won't disconnect the graph. Therefore, the core task of the algorithm is to determine, for each edge, whether a cycle exists that includes it. Tarjan's method achieves this by augmenting DFS with two timestamps for each vertex: its discovery time and its low-link value.

Discovery Time and Low-Link Value

As the DFS progresses, you assign each vertex $u$ a discovery time $disc[u]$. This is a simple counter that increments each time a new vertex is visited, providing a unique chronological order of discovery. It represents the earliest time you encountered that vertex.

The more sophisticated metric is the low-link value, denoted $low[u]$. This value represents the earliest discovery time reachable from vertex $u$ by traversing its descendants in the DFS tree and then using, at most, one back edge. Formally, $low[u]$ is the minimum of:

1. Its own discovery time: $disc[u]$.
2. The discovery times of vertices connected via back edges from $u$ (i.e., $disc[v]$ for any back edge $(u,v)$).
3. The low-link values of its children in the DFS tree (i.e., $low[child]$ for each tree edge child).

You compute $low[u]$ recursively during the DFS backtracking phase. This value answers a critical question: "What is the highest (closest to the root) ancestor I can reach from this subtree without using the edge I came in on?"

The Bridge Condition Rule

The magic happens when you process an edge $(u,v)$ during DFS, where $u$ is the parent of $v$. After recursively computing $low[v]$ for the child vertex, you can test for a bridge with this condition:

An edge $(u,v)$ is a bridge if and only if $low[v]>disc[u]$.

Let's interpret this inequality. $disc[u]$ is the time you discovered the parent $u$. $low[v]$ is the earliest reachable discovery time from the child's subtree. If $low[v]$ is greater than $disc[u]$, it means that from $v$ (and all vertices in its subtree), there is no path back to $u$ or any of its ancestors that doesn't use the edge $(u,v)$ itself. Therefore, the subtree rooted at $v$ is isolated from the rest of the graph if $(u,v)$ is removed—the very definition of a bridge.

Conversely, if $low[v]\le disc[u]$, then a path exists from $v$ back to $u$ (or an ancestor of $u$) via a back edge, forming a cycle that includes $(u,v)$. This edge is not a bridge. Back edges, which connect to vertices with lower discovery times, are the mechanism that reduces low-link values and prevents edges from being classified as bridges.

Algorithm Walkthrough and Implementation

The algorithm is a modified DFS. You maintain a timer, disc[] and low[] arrays, and a parent pointer to avoid traversing the immediate parent-child edge in reverse (which is not a back edge in an undirected graph).

Here is a conceptual step-by-step for a graph starting at an arbitrary vertex:

1. Initialize all disc and low values as unvisited (e.g., -1). Set time = 0.
2. Begin DFS at a vertex u. Set disc[u] = low[u] = ++time.
3. For each neighbor v of u:

• If v is unvisited (tree edge):
• Recursively DFS v.
• After returning, update: $low[u]=min(low[u],low[v])$.
• Check the bridge condition: if $low[v]>disc[u]$, then edge (u, v) is a bridge.
• Else if v is already visited and v is not the parent of u (back edge):
• Update: $low[u]=min(low[u],disc[v])$.

This process runs in $O(V+E)$ time because it is essentially a DFS with constant-time operations per edge. The space complexity is $O(V)$ for the arrays and recursion stack.

Example: Consider a simple graph: vertices 0-1-2 in a line (edges: 0-1, 1-2). Starting DFS at 0:

• disc[0]=1, low[0]=1. Discover 1.
• disc[1]=2, low[1]=2. Discover 2.
• disc[2]=3, low[2]=3. Vertex 2 has no more neighbors. Backtrack to 1.
• Check edge (1,2): $low[2]=3>disc[1]=2$ → Bridge.
• Update $low[1]=min(2,3)=2$. Backtrack to 0.
• Check edge (0,1): $low[1]=2>disc[0]=1$ → Bridge.

Application to Network Reliability and Biconnected Components

The primary application of bridge-finding is network reliability assessment. In a communication or transport network modeled as a graph, bridges represent single points of failure. Identifying them allows network engineers to prioritize reinforcing these connections with additional links (redundancy) to create a more robust, biconnected network where no single edge removal disconnects it.

This leads directly to the algorithm's extension: finding biconnected components (also known as blocks or 2-connected components). A biconnected component is a maximal subgraph with no articulation points (vertices whose removal disconnects the graph). Importantly, two biconnected components can share at most one vertex (an articulation point), and they are separated from each other by bridges. You can modify Tarjan's bridge-finding algorithm to use a stack. During DFS, you push edges onto a stack. When you find a bridge (or reach the end of a subtree with $low[v]\ge disc[u]$), you pop edges from the stack until you pop the current edge $(u,v)$; all these popped edges form one biconnected component. This extension powerfully segments a graph into its resilient, highly-connected regions.

Common Pitfalls

1. Ignoring Parent Check in Back Edge Detection: In an undirected graph, the edge $(u,v)$ is bidirectional. When exploring from u, if you encounter a visited neighbor v, you must check that v is not the immediate parent of u. If you don't, you will incorrectly treat the parent-child edge (a tree edge) as a back edge, which can falsely lower a low value and cause you to miss a bridge. Always pass and use the parent's identifier in the DFS call.

1. Using low[v] Instead of disc[v] for Back Edge Updates: When you encounter a back edge from u to an already-visited ancestor v, the correct update is $low[u]=min(low[u],disc[v])$, not $low[v]$. You are establishing a connection from u directly to the discovery time of v, not to the lowest point v can reach. Using $low[v]$ here can propagate low-link values incorrectly across disconnected parts of the DFS tree.

1. Misinterpreting the Bridge Condition for the Root: The condition $low[v]>disc[u]$ holds universally. However, for the DFS root node (which has no parent), this test is not applied. A special case arises when checking for articulation points (a related algorithm), but for bridge-finding, you simply don't test a non-existent parent edge. Confusing the rules for bridges and articulation points is a frequent error.

1. Assuming One DFS Call is Enough for Disconnected Graphs: The standard algorithm description often starts from a single vertex. In a disconnected graph, a single DFS will only traverse one connected component. You must wrap the DFS initiation in a loop that starts a new DFS from each unvisited vertex. This ensures all bridges across the entire graph are found, while still maintaining the overall $O(V+E)$ complexity.

Summary

• A bridge is an edge whose removal disconnects an undirected graph, meaning it is not part of any cycle.
• Tarjan's algorithm finds all bridges in $O(V+E)$ time by performing a modified DFS that tracks each vertex's discovery time ($disc[u]$) and low-link value ($low[u]$), the earliest ancestor reachable from its subtree.
• The core rule is: a tree edge $(u,v)$ is a bridge if and only if $low[v]>disc[u]$. If $low[v]\le disc[u]$, a back edge creates a cycle, making the edge non-critical.
• The algorithm is directly applied to assess network reliability, as bridges are single points of failure. It can be extended using a stack to partition the graph into biconnected components.
• Key implementation pitfalls include properly handling parent pointers to avoid mislabeling tree edges, correctly updating low values using $disc[v]$ for back edges, and ensuring the DFS visits all connected components in a disconnected graph.