Introduction

Finding whether a given edge is part of a Minimum Spanning Tree (MST) in linear time is an intriguing problem within the realm of graph algorithms. It essentially asks if, given a weighted, connected, and undirected graph $G = (V, E)$, we can determine if an edge $e$ is part of an MST in linear time with respect to the number of edges $|E|$ in the graph.

This problem is important in network design, optimization, and understanding the dynamics of connectivity within a graph. In this article, we will delve into the theory and methodology behind determining the presence of an edge in an MST efficiently.

Concepts and Prerequisites

Minimum Spanning Tree (MST)

A Minimum Spanning Tree is a subset of the edges of a graph that connects all vertices with the minimum total edge weight, forming no cycle. Some foundational algorithms to find an MST include Kruskal’s and Prim’s algorithms, both of which typically run in $O(E \log V)$ time.

Fundamental Cut Property

The fundamental cut property states that for any cut in the graph, the lightest edge crossing the cut must be part of the MST. This is crucial for determining whether a given edge belongs to an MST.

Edge Detection in MST: Theory

To determine if an edge $e$ is part of the MST, we need to rely on the properties of the MST:

1. Critical Edge: If removing edge $e$ increases the weight of the MST, $e$ is a critical edge and part of every MST.
2. Cycle Property: For any cycle in the graph, the heaviest edge in that cycle cannot belong to the MST.

Linear-Time Algorithm

The problem can be tackled in linear time $O(E)$ using an algorithm based on Depth First Search (DFS) that leverages properties such as tree and forward edge detection:

1. DFS Preprocessing:
   • Start a DFS from any vertex of the graph.
   • For each edge $e$, determine its type (tree, back, etc.).
2. Edge Examination:
   • For the edge $e = (u, v)$, perform the following:
     • Conduct DFS to classify edges and determine the order of discovery (pre-order and post-order numbering).
     • Determine if $e$ forms a cycle in conjunction with tree edges in the DFS tree.
     • Perform a traversal to check if $e$ is the maximum weighted edge along any path between the two vertices.
3. Edge Analysis:
   • Check if the edge $e$ remains the minimum or fits into the collective weight properties of crossing the cut.
   • Verify if removing edge $e$ disconnects the graph when DFS spans from either subtree it once connected.

Example

Consider the following graph and edge: